Я долгое время думал, что написать сортировку массива слиянием так, чтобы она не использовала дополнительной памяти, но чтобы время работы оставалось равным O(N*log(N)), невозможно. Поэтому, когда karlicos поделился ссылкой на описание такого алгоритма, меня это заинтересовало. Поиск по сети показал, что про алгоритм люди знают, но никто им особо не интересуется, его считают сложным и малоэффективным. Хотя, может быть, они имеют в виду какую-то «стабильную» версию этого алгоритма, но нестабильная при этом все равно никому не нужна.
Но я все-таки решил попробовать.
Слияние за линейное время
Идея алгоритма довольно простая. Все, что нам нужно – это слить две упорядоченные части одного массива за O(N) сравнений и обменов элементов. Делается это так:Выбираем число S≈sqrt(N)
Делим массив на K кусков длины S. Остаток, не попавший ни в один из кусков, пока не трогаем
Кусок, в который попала граница между упорядоченными фрагментами, меняем с последним куском. Это будет наш буфер обмена
Сортируем K-1 оставшийся кусок по возрастанию первых элементов. Здесь нам нужно использовать алгоритм, линейный по числу обменов. Подходит сортировка выбором минимального элемента.
Замечаем две важные вещи. Во-первых, если у нас есть два поряд идущих отсортированных фрагмента длиной A и B и буфер обмена, длина которого не меньше min(A,B), то мы можем слить эти фрагменты, затратив не более A+B сравнений и A+B+min(A,B) обменов. Порядок элементов в буфере обмена при этом может измениться. Во-вторых, при сортировке полученного на предыдущем шаге массива из (K-1)*S элементов, каждый элемент может сдвинуться не более, чем на S позиций влево, т.е. никогда не окажется левее предыдущего «куска».
Пользуясь буфером обмена, последовательно сливаем пары соседних кусков – [0..S-1] и [S,2*S-1], потом [S,2*S-1] и [2*S,3*S-1], и т.д. Из предыдущего пункта следует, что в результате мы получим отсортированный массив из M=S*(K-1) элементов
Сортируем последние R=N-M элементов исходного массива (буфер обмена+остаток) любым алгоритмом. Они рекомендуют какой-нибудь квадратичный алгоритм (для чистоты идеи, чтобы избежать рекурсии), но с практической точки зрения, рекурсивный вызов сортировки не хуже.
Сливаем отсортированные фрагменты массива [R..N-R-1] и [N-R..N-1], используя фрагмент [0..R-1] как буфер обмена
Ищем на стыке предыдущего и следующего пунктов ошибку в алгоритме. Если не найдете – она объясняется в конце статьи
Сортируем буфер обмена: в нем были и остались R младших элементов массива, и после сортировки они окажутся на месте
Описание довольно длинное, но понять можно. Число обменов на одно слияние – примерно 5*N, число сравнений – около 6*N (оно зависит от длины остатка). Для полной сортировки эти числа умножаются на log(N), и получается много.
Адаптация алгоритма для сортировки
Чтобы нам было попроще, а алгоритм работал эффективнее, заметим следующее.Вся возня с буфером обмена и его последующее слияние с массивом нужны только если в массиве в самом деле не было свободного места. Если мы сливаем фрагменты длиной A и B, а после них есть еще хотя бы S ячеек неотсортированного пространства, то нам достаточно разбить массивы на куски, отсортировать их и слить. Особенно эффективно это будет работать, если S=A=B.
Надо постараться, чтобы длина остатка была нулевой, а граница между отсортированными фрагментами попала точно на границу кусков длины S. Проще всего этого добиться, если выбрать S равным степени двойки, а A и B заставить делиться на него.
Сортировка кусков массивов требует ((A+B)/S)2/2 сравнений. Последующая сортировка буфера обмена – O(S*log( S )) сравнений. Поэтому выбирать S близким к sqrt(N) не обязательно, можно увеличить его, например, до N/log(N).
Вооружившись этими мыслями, пишем программу (пока только для массива типа int[]). Сначала сортируем и сливаем фрагменты с длинами, равными степени двойки, причем идем строго слева направо, чтобы правее было свободное место. Когда дойдем до буфера обмена, сливаем неслитые, но отсортированные фрагменты. Сортируем буфер обмена+остаток, сливаем результат с остальной частью массива, сортируем вновь получившийся буфер обмена — и массив отсортирован. Получается алгоритм примерно в сотню строк. Правду сказали, что он громоздкий. А как насчет эффективности?
Честно говоря, я надеялся, что он проиграет стандарному qsort не более 3 раз. Но сравнение в реальных условиях (на массивах длиной до 108) показало, что по числу сравнений алгоритм выигрывает у qsort примерно 10%, а по общему времени работы – от 1.2 до 1.3 раз! Возможно, это связано с тем, что функция icmp (сравнение двух целых чисел по данным адресам) подставляется inline – но код, который вставляется, получается довольно ужасным (я проверял).
В целом, все не так плохо, как говорили.
А что же за ошибка была в описании алгоритма? Дело в том, что если в буфер обмена или в остаток попал элемент, который после сортировки должен находиться в одной из первых R позиций, то в итоге он на место никак не попадет. Для исправления приходится следить, на какое место попал при последнем слиянии элемент, находившийся в ячейке с индексом R, и финальную сортировку делать начальному фрагменту до этого места (его длина может быть несколько больше чем R).
