MergeSort + InsertionSort + хитрые эвристики = ?
Сортировка массива — базовая операция. Каждый программист может написать несколько, а просто назвать алгоритмов сортировки — ещё больше.
«Естественная» необходимость и любовь к красивым решениям дала нам MergeSort, QuickSort, HeapSort и т.д. Самоирония, видимо, породила такие алгоритмы, как StupidSort, SleepSort и мой любимый — TwitterSort.
Что же использует Python? TimSort!
Автором является широко известный в узких кругах Тим Питерс, а сам алгоритм был с портирован в Java и Android.
Это гибридный адаптивный алгоритм, который совмещает под капотом MergeSort, InsertionSort и хитрые эвристики. Алгоритм ищет в сортируемой последовательности длины N уже отсортированные подпоследовательности (run). Если такая подпоследовательность меньше определённого порогового значения (min_run), то идущие за ней дальше элементы «досортировываются» с помощью InsertionSort, пока критерий не будет удовлетворен.
В итоге, исходная последовательность превращается в N/min_run отсортированных run’ов. Run’ы сливаются последовательно и попарно, память выделяется только на элементы, которые действительно нужно перемещать.
Допустим есть две подпоследовательности: A = [1, 2, 8, 9] и B = [4, 5,10, 21, 42]
В них 1, 2, 10, 21 и 42 уже находятся на своих финальных местах, что можно определить бинарным поиском B[0] в A и A[-1] в B. Память выделяется (и туда копируются) только на элементы из меньшей подпоследовательности, которые не стоят на своих финальных местах: 8 и 9. Дальше происходит слияние временной выделенного участка памяти и B с переносом элементов в A.
Galloping
И, конечно, нельзя не упомянуть про режим галопа. В нём во время слияния элементы перемещаются не попарным сравнением, а сразу целой «пачкой». Если сливаются temp = [8, 9] и B = [4, 5, 10, 21, 42] в A = [1, 2, , ], то поиском temp[0] в B можно определить, что элементы 4 и 5 нужно сразу перенести в A, после чего останется только дописать 8 и 9 в B.
И это ещё не все тонкости! Как выбирать min_run? Как искать элемент в массиве в режиме галопа? Для каких последовательностей сразу использовать InsertionSort без всей описанной «мишуры»? Есть в чём покопаться.
Спрашивайте в комментариях, если возникнут вопросы!