Pull to refresh

Сортировка слиянием без использования дополнительной памяти

Algorithms *
Я долгое время думал, что написать сортировку массива слиянием так, чтобы она не использовала дополнительной памяти, но чтобы время работы оставалось равным 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).

UPD: В алгоритме, как я его здесь описал, обнаружилась еще одна ошибка, относящаяся к «сортировке кусков массива». В случае, если в исходном массиве много одинаковых элементов, у разных кусков из одного фрагмента массива могут оказаться одинаковые первые элементы. И если порядок, в котором идут эти куски, при сортировке будет нарушен, то результат сортировки всего массива может оказаться неверным.

Для борьбы с этим эффектом при сортировке надо сравнивать первые элементы кусков, а если они одинаковы — сравнить последние элементы. И сортировать куски лексикографически по этим парам элементов.
Tags:
Hubs:
Total votes 40: ↑38 and ↓2 +36
Views 34K
Comments Comments 67