Чтобы не быть голословным и доставить удовольствие местным анонимным икспёртам.
Текущая сортировка внутри libmdbx показывает такие циферки:---
Эльбрус E8C, компилятор lcc:1.23.19:Jun-19-2019:e2k-v4-linux
random, 11 items std::sort: 413.168 ticks, ok
mdbx: 96.050 ticks 430.16% speed, ok
mixed, 11 items std::sort: 400.129 ticks, ok
mdbx: 96.050 ticks 416.58% speed, ok
random, 111 items std::sort: 6750.706 ticks, ok
mdbx: 4671.339 ticks 144.51% speed, ok
mixed, 111 items std::sort: 4541.049 ticks, ok
mdbx: 2836.840 ticks 160.07% speed, ok
random, 1111 items std::sort: 93208.344 ticks, ok
mdbx: 77806.556 ticks 119.79% speed, ok
mixed, 1111 items std::sort: 52042.322 ticks, ok
mdbx: 40537.589 ticks 128.38% speed, ok
random, 11111 items std::sort: 1200639.556 ticks, ok
mdbx: 1085497.222 ticks 110.61% speed, ok
mixed, 11111 items std::sort: 819688.111 ticks, ok
mdbx: 618397.111 ticks 132.55% speed, ok
---
Intel x86-64, компилятор gcc 9.2.1
random, 11 items std::sort: 439.045 ticks, ok
mdbx: 60.506 ticks 725.62% speed, ok
mixed, 11 items std::sort: 113.641 ticks, ok
mdbx: 47.006 ticks 241.76% speed, ok
random, 111 items std::sort: 7217.518 ticks, ok
mdbx: 5166.508 ticks 139.70% speed, ok
mixed, 111 items std::sort: 2533.239 ticks, ok
mdbx: 1952.844 ticks 129.72% speed, ok
random, 1111 items std::sort: 101895.956 ticks, ok
mdbx: 88060.700 ticks 115.71% speed, ok
mixed, 1111 items std::sort: 42254.344 ticks, ok
mdbx: 32174.811 ticks 131.33% speed, ok
random, 11111 items std::sort: 1431319.556 ticks, ok
mdbx: 1240181.444 ticks 115.41% speed, ok
mixed, 11111 items std::sort: 688404.444 ticks, ok
mdbx: 486213.778 ticks 141.58% speed, ok
---
Intel x86-64, компилятор clang 9.0
random, 11 items std::sort: 270.146 ticks, ok
mdbx: 42.616 ticks 633.91% speed, ok
mixed, 11 items std::sort: 97.677 ticks, ok
mdbx: 42.713 ticks 228.68% speed, ok
random, 111 items std::sort: 8251.918 ticks, ok
mdbx: 5323.947 ticks 155.00% speed, ok
mixed, 111 items std::sort: 2792.332 ticks, ok
mdbx: 2016.517 ticks 138.47% speed, ok
random, 1111 items std::sort: 120649.822 ticks, ok
mdbx: 92747.533 ticks 130.08% speed, ok
mixed, 1111 items std::sort: 41854.211 ticks, ok
mdbx: 33450.478 ticks 125.12% speed, ok
random, 11111 items std::sort: 1520248.667 ticks, ok
mdbx: 1198299.667 ticks 126.87% speed, ok
mixed, 11111 items std::sort: 711888.222 ticks, ok
mdbx: 504380.000 ticks 141.14% speed, ok
---
Intel x86-64, компилятор gcc 7.4 (тут хуже, потому что до 9.x у gcc плохо с CMOV).
random, 11 items std::sort: 242.481 ticks, ok
mdbx: 202.167 ticks 119.94% speed, ok
mixed, 11 items std::sort: 100.371 ticks, ok
mdbx: 58.314 ticks 172.12% speed, ok
random, 111 items std::sort: 7136.350 ticks, ok
mdbx: 7360.917 ticks 96.95% speed, ok
mixed, 111 items std::sort: 2634.730 ticks, ok
mdbx: 2448.223 ticks 107.62% speed, ok
random, 1111 items std::sort: 105528.567 ticks, ok
mdbx: 107678.700 ticks 98.00% speed, ok
mixed, 1111 items std::sort: 39723.067 ticks, ok
mdbx: 36326.300 ticks 109.35% speed, ok
random, 11111 items std::sort: 1389003.667 ticks, ok
mdbx: 1409333.000 ticks 98.56% speed, ok
mixed, 11111 items std::sort: 651409.667 ticks, ok
mdbx: 558271.000 ticks 116.68% speed, ok
На всякий: машины разные, тики посчитаны посредством MFENCE+RDTSC (выбираются лучшие для 100 повторов и усредняются за несколько прогонов с разными данными), сравнивать их между собой не совсем корректно.
С "random"-паттерном думаю все очевидно, а "mixed" - это симуляция наиболее частого случая при работе MDBX (половина данных отсортирована, четверть в обратном порядке, еще четверть в случайном порядке).