Comments 3
Отличная статья. Спасибо.
Спасибо! Есть варианты, которым можно поучится.
Ну и, если обычная сортировка слиянием имеет лучшую алгоритмическую скорость O(n log n), то у вики-сортировки этот показатель равен O(n). До недавнего времени считалось, что сортировка слиянием с таким набором характеристик невозможна в принципе, но китайские программисты всех удивили.
Я конечно некромант, но...
O(n) это же в лучшем случае. В сортировке слияниями для этого достаточно сравнить смыкаемые края при слиянии, если массив отсортирован, то достаточно (N -1) сравнений.
Sign up to leave a comment.
Гибридные сортировки