Ненайдя промышленной реализации метода сортировки bottom-up heapsort, решил реализовать этот алгоритм самостоятельно, с небольшой модификацией.
Исходный код можно посмотреть на Github: github.com/Maxime2/heapsort
Bottom-up heapsort (bottom-up-heapsort) является вариантом алгоритма сортировки heapsort (пирамидальной сортировки) с новой процедурой восстановления пирамиды. Этот варианд превосходит, в среднем, алгоритм быстрой сортировки (quicksort), если n > 2400, и модифицированный вариант быстрой сортировки с выбором ведущего элемента как медианы 3 элементов массива, если n > 16000.
Алгоритм bottom-up heapsort описан в работе Ingo Wegener, BOTTOM-UP-HEAPSORT, a new variant of HEAPSORT beating, on an average, QUICKSORT (if n is not very small), Theoretical Computer Science 118 (1993), pp. 81-98, Elsevier.
Добавленная мной модификация, позволяющая дополнительно сэкономить (n-2)/2 операций обмена и (n-2)/2 операций сравнения, при n > 3, основана на идее отложенного восстановления пирамиды после перемешения корневого элемента на его место, найденной в работе D. Levendeas, C. Zaroliagis, Heapsort using Multiple Heaps, in Proc. 2nd Panhellenic Student Conference on Informatics -- EUREKA. – 2008. – P. 93–104.