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

    Я долгое время думал, что написать сортировку массива слиянием так, чтобы она не использовала дополнительной памяти, но чтобы время работы оставалось равным 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: В алгоритме, как я его здесь описал, обнаружилась еще одна ошибка, относящаяся к «сортировке кусков массива». В случае, если в исходном массиве много одинаковых элементов, у разных кусков из одного фрагмента массива могут оказаться одинаковые первые элементы. И если порядок, в котором идут эти куски, при сортировке будет нарушен, то результат сортировки всего массива может оказаться неверным.

    Для борьбы с этим эффектом при сортировке надо сравнивать первые элементы кусков, а если они одинаковы — сравнить последние элементы. И сортировать куски лексикографически по этим парам элементов.
    Метки:
    Поделиться публикацией
    Реклама помогает поддерживать и развивать наши сервисы

    Подробнее
    Реклама
    Комментарии 67
    • 0
      судя по описанию алгоритма, они ничем не отличается от обычной сортировки слиянием, кроме месторасположения буфера обмена.
      • +2
        Буфер обмена находится в том же массиве, в котором находятся данные. И, соответственно, содержит часть этих данных. При этом никакие данные при сортировке не теряются (все операции — обмены элементов), и, в конечном итоге, содержимое «буфера обмена» оказывается всортированным в общий массив.
        • 0
          Не используйте qsort(), разве что когда пишете на чистом Си. Используя qsort() вместо std::sort() вы препятствуете инлайнингу и методично отбрасываете всю ту информацию о типах, которая изначально была.
          • +2
            Попробую. Заодно вспомню, как с этим работать.
            • +2
              Попробовал. Выигрыш по времени сократился до 10%, а по числу сравнений — увеличился до 1.5 раз.
            • +1
              С таким quick sort сравните.
              • 0
                Мой код примерно вдвое медленнее.
                • 0
                  UPD. После небольшой оптимизации разрыв сократился до 1.3 раза. У vector.sort алгоритм теперь выигрывает 1.6-1.7 раза по времени.
                  • 0
                    Странно быстрый какой-то алгоритм Ваш. Колдовство. Надо будет разобраться, может это новый лидер?)
                    • 0
                      Лидер среди кого? Гарантированных O(N*log(N)) с не более, чем log(N) дополнительной памяти? Не знаю, я давно за прогрессом не следил. Думаю, что на «почти отсортированных массивах» мой алгоритм проиграет. Обогнать базовый merge (с N/2 дополнительной памяти) и хорошо написанный QuickSort (по среднему времени) практически нереально. Ну, и неизвестно, что будет на других типах (не на int) и при передаче функции сравнения параметром.
                      • 0
                        Насколько я понял, предложенная сортировка есть In-Place Merge Sort, неплохо гуглится (например вот или вот. В англ. вики отметили, что сортровка слиянием является эффективней быстрой сортировки на структурах с последовательным доступом.
                        • 0
                          Когда я пытался разобраться в первом из этих алгоритмов, мне показалось, что он квадратичный по времени. Возможно, я ошибаюсь — надо будет проверить их на скорость. Но в комментариях ничего не говорится про число операций.
                          Что касается «структур с последовательным доступом» — имеются в виду связанные списки? Так с ними все ясно — для них сортировка слиянием пишется легко, за log(N) памяти. На этом основано, в частности, перемножение разреженных многочленов за M*N*log(min(M,N)) операций, где M и N — число мономов в операндах.
                          • 0
                            Первый алгоритм интересный. Чтобы слить две отсортированные части массива, они делят длинную часть пополам (на части A1 и A2), потом короткую часть B делят на две части B1 и B2 так, чтобы max(B1)<=min(A2), min(B2)>=max(A1). Потом переставляют фрагменты A2 и B1, и сливают A1 c B1, а A2 с B2.
                            Как вы думаете? Это гарантированное N*log(N)? Если да, то константа довольно большая — в среднем он в 6-7 раз медленнее, чем msort (экспериментальный результат).
                            • 0
                              Нет, N*log(N) — только на merge. На всю сортировку N*log(N)^2. Оно и видно.
                              • +1
                                а если вместо слияния A1 с B1 и A2 с B2 задать рекурсию, которая будет разбивать на части и переставлять до массива из двух переменных?
                                • 0
                                  Так ведь «слияние» — это и есть рекурсия. Которая переставляет части, разбивает их на более мелкие куски, снова переставляет… Проблема в том, что на каждом уровне глубины рекурсии приходится переставлять примерно N/2 элементов — в итоге мы получаем O(N*log(N)) обменов.
                                  • 0
                                    я уже говорю про ту часть, когда у нас есть два отсортированных подмассива, и надо слить в один, для этого использовать другую рекурсию, где сначала создаются A1 A2 B1 B2, B1 и A2 меняются местами и эта же операция выполняется для A1 B1 и A2 B2
                                    В итоге эта рекурсия в худшем случае займёт дополнительно N*log(N) операций
                                    • 0
                                      Правильно, так и делается. Merge проходит за N*log(N) операций. А для полной сортировки массива его надо вызвать на log(N) уровнях, и на каждом он потребует N*log(K) операций, где K — длина фрагментов, которые мы сливаем на этом уровне (сначала по 2, потом по 4 элемента и т.д.). В сумме выйдет O(N*log(N)^2) обменов на всю сортировку.
                  • 0
                    Тот код на плюсах написан, а у автора — чистый С, что иногда бывает очень даже нужно.
                    • 0
                      Там заменить template на #define — и будет еще более чистый C. Даже все переменные в начале описаны.
                      • 0
                        Лучше, наверное, будет не #define делать, а просто сделать свою функцию сортировки для каждого типа данных (sortf, sortd, sorti и т.п.), как это, по сути, и реализуется в плюсах после разворачивания компилятором кода с шаблоном.
                        • +1
                          Да. И чтобы не дублировать код, сделать это как-нибудь так:
                          #define T int
                          #define ___sort sorti
                          #include «quicki.c»
                          #undef ___sort
                          #undef T

                          #define T float
                          #define ___sort sortf
                          #include «quicki.c»
                          #undef ___sort
                          #undef T

                          и так далее. Наверное, можно как-нибудь красивее, но лень искать.
                  • 0
                    Объясните про «Здесь нам нужно использовать алгоритм, линейный по числу обменов. Подходит сортировка выбором минимального элемента.» Имеется ввиду, что К заранее известно, является небольшим числом и сортировка проходит «в ручную» заранее запрограммированной сортирующей сетью? — тогда там не линейный алгоритм со сложностью O(n*log(n)). Если К заранее неизвестно, то сложность сортировки выбором минимального элемента — O(n^2)
                    • 0
                      Нет, K неизвестно. И число сравнений при сортировке может быть O(K^2). Но вот число реальных перемещений данных должно быть O(K). В самом деле, каждый блок занимает S элементов, и даже если мы выберем алгоритм, работающий за O(K*log(K)) сравнений и O(K*log(K)) обменов, то полное время работы этапа алгоритма будет O(N*log(K)) (где N=S*K) — сравнение двух блоков идет за O(1), а обмен за O(S) — а это слишком много. Поэтому, берется алгоритм со сложностью O(K) обменов и O(K^2) сравнений. Если S>=sqrt(N), то сложность сортировки блоков будет O(N).
                      • 0
                        github.com/swenson/sort — Shell sort, Binary insertion sort, Heap sort, Quick sort, Merge sort, Bubble sort (ugh), Tim sort в виде макросов.
                        Особенно рекомендую попробовать Tim sort.
                        • 0
                          Заставить его работать под Visual Studio толком не удалось. Кое-как добился, что он компилируется, но в итоге tim_sort, хоть и запустился, стал выдавать неправильные результаты. И тратить на это в 1.4 раза больше времени, чем мой алгоритм.
                          • 0
                            Хм. Интересно, как вам это удалось… У меня конкретно этот код работает под хорошей такой нагрузкой последние три месяца.
                            Правда, никакого Visual Studio — только Linux, только хардкор ©.
                            • 0
                              Удалось легко — я забыл закомментарить строчку
                              #define SORT_CMP(x, y) (x — y)
                              В результате сравнение стало нетранзитивным. После исправления алгоритм заработал. На большинстве тестов он в 1.8 раза медленнее, чем мой, но один раз (на массиве размером 12.5 млн) выдал время 27 секунд против 1.6 (т.е. проиграл 17 раз).
                              • 0
                                Пересобрал под x64. Разрыв скорости сократился до 15%.
                                • 0
                                  Ок, вы меня заинтересовали =) Как собрать ваш пример?
                                  Споткнулся на этом:
                                  mmerge.cpp: In function ‘void msort(int*, int)’:
                                  mmerge.cpp:105:15: error: ‘s’ was not declared in this scope
                                  • 0
                                    Странно. Переменная s описана в предыдущей строчке. Возможно, я где-то не до конца соблюдаю стандарт языка: на C++ я пишу в среднем 2 раза в год, так что многое мог забыть или вообще не знать.
                                    • 0
                                      Там почему-то была 'a', а не 's'. Ну да бог с ним, не важно.

                                      Действительно, на рандомных данных tim sort выходит процентов на 12-15 медленнее, чем этот алгоритм. Любопытно.

                                      Я только не совсем понял — как этот подвид merge sort называется? merge sort with extra memory? А где тут extra memory?
                                      • 0
                                        Он называется «In-Place Merge Sort». Выше уже были комментарии об этом. Как называется подвид, работающий за N*log(N), и выделяется ли он вообще в отдельный класс — не знаю.
                                        • 0
                                          Не возражаете, если я его сюда github.com/swenson/sort добавлю?
                                          (и что написать в копирайте?)
                                          • 0
                                            В алгоритме есть логическая ошибка. Поэтому пока отправлять не стоит :) Надеюсь, что я ее смогу быстро исправить.
                                            • 0
                                              Ошибку исправил, файл выгрузил на astr73.narod.ru/Files/msort.cpp
                                              Так что можно добавлять. Копирайт там внутри поставлен, © Andrey Astrelin.
                                              • +1
                                                Ok, here you go: github.com/tony2001/sort/

                                                Комментарии приветствуются.
                                                Можно просто собрать и прогнать тесты.

                                                demo на 100000 даёт такой результат:
                                                Running tests
                                                stdlib qsort time: 13593.00 us per iteration
                                                quick sort time: 7162.00 us per iteration
                                                bubble sort time: 16568472.00 us per iteration
                                                merge sort time: 9386.00 us per iteration
                                                binary insertion sort time: 1676846.00 us per iteration
                                                heap sort time: 11884.00 us per iteration
                                                shell sort time: 12984.00 us per iteration
                                                tim sort time: 10967.00 us per iteration
                                                in-place merge sort time: 8215.00 us per iteration < — NB
                                    • 0
                                      Ну так тестировать то надо не на случайных данных.
                                      на случайных данных тимсорт примерно 10-15 процентов и проигрывает стандартному мерджсорту

                                      а вот если взять упорядоченный массив и слегка его «попортить» перестановками, то тим сорт раза в 2 уже выигрывает
                                      • 0
                                        Сравнил msort, std::sort и timsort в разных ситуациях (правда, msort пришлось слегка подправить, чтобы он не портил уже отсортированные участки).
                                        Длина массива была одинаковой — N=10^8 элементов.
                                        В первом тесте массив заполнялся случайными целыми числами.
                                        В втором и третьем тестах числа брались из ограниченного диапазона — от 0 до 19 и от 0 до 999 соответственно (т.е. было много одинаковых элементов).
                                        В следующих трех тестах массив состоял из отсортированных блоков (длиной 7, 97 и 9997 элементов соответственно).
                                        В двух последних тестах брался отсортированный массив в нем делалось несколько случайных транспозиций — N/2 и N/8 соответственно (т.е. примерно 0.36*N элементов в первом случае и 0.78*N — во втором оставались на местах).
                                        Результаты (время — в миллисекундах):

                                        Random
                                        msort: Ok, time=21044
                                        std::sort: Ok, time=22027
                                        TimSort: Ok, time=30030

                                        20 different values
                                        msort: Ok, time=13416
                                        std::sort: Ok, time=3260
                                        TimSort: Ok, time=21341

                                        1000 different values
                                        msort: Ok, time=15896
                                        std::sort: Ok, time=7894
                                        TimSort: Ok, time=24804

                                        sorted blocks of length 7
                                        msort: Ok, time=20598
                                        std::sort: Ok, time=22090
                                        TimSort: Ok, time=29703

                                        sorted blocks of length 97
                                        msort: Ok, time=18657
                                        std::sort: Ok, time=20919
                                        TimSort: Ok, time=21356

                                        sorted blocks of length 9997
                                        msort: Ok, time=14399
                                        std::sort: Ok, time=18751
                                        TimSort: Ok, time=14851

                                        swapped N/2 pairs
                                        msort: Ok, time=17924
                                        std::sort: Ok, time=20904
                                        TimSort: Ok, time=25849

                                        swapped N/8 pairs
                                        msort: Ok, time=13519
                                        std::sort: Ok, time=16520
                                        TimSort: Ok, time=20545
                                        • 0
                                          О, а есть код этих тестов?
                                          Я бы прогнал их на алгоритмах из sort.h чисто любопытства ради.
                                          • 0
                                            Выгрузил свежую версию алгоритма вместе с кодом тестов туда же: astr73.narod.ru/Files/msort.cpp
                                            • +1
                                              ок, добавил.
                                              результаты тестов тут: pastebin.com/v0PcruiR
                                              • 0
                                                Спасибо. Это на какой длине массива?
                                                • 0
                                                  там тысяча прогонов с рандомной длиной массива от 0 до 25600.
                                                  размеры массивов генерятся 1 раз для всех тестов.
                                                  • 0
                                                    Жесткие условия…

                                                    image
                                                    • 0
                                                      Автор sort.h спрашивает — вы согласны законтрибутить код под лицензией MIT?
                                                      • 0
                                                        Думаю, да. А что ему показалось похожим на tim sort? Если алгоритм в целом — то у них почти ничего общего (кроме слова merge)
                                                        • 0
                                                          Не знаю. Но думаю, что вряд ли можно понять алгоритм за несколько минут =)
                                                          • 0
                                                            Да, особенно нерекурсивный merge sort, основанный на двоичном разложении индекса :D
                                                            Попробую еще добавить эффективную сортировку четверок последовательных элементов. Может быть, чего-нибудь выиграю.
                                                            Кстати, merge sort с дополнительным буфером, написанный в том же стиле, быстрее, чем msort, всего на 10-15%.
                                                        • 0
                                                          А про CLZ пишут, что она только для архитектуры ARM :(
                                                          • 0
                                                            у него там рядом своя имплементация, с этим проблем нет.
                                                          • 0
                                                            И где он увидел in-place merge в tim sort? Строчка
                                                            TIM_SORT_RESIZE(store, MIN(A, B));
                                                            показывает, что он совсем не in-place, а использует дополнительную память.
                                                    • 0
                                                      Интересно, что простой merge стал сильно лучше, чем в тесте на 100000.
                                  • +2
                                    Похоже, что критически важным для данного теста является отстутствие встраиваимости сравнения в std::sort. После того, как вместо указателя на функцию передан функциональный объект (lambda), или используется сравнение по-умолчанию, std::sort ускоряется почти в 2 раза.

                                    Немного скорректировал тест:
                                    — Убрал инициализацию вектора (по ошибке время его создания учитывалось для теста std::sort)
                                    — Сортировка отлично работает для массивов, вообще убрал std::vector (но это не думаю, что важно)
                                    — Убрал подсчёт сравнений из всех тестов, и передал функциональный объект (lambda). Попробовал без собственного компаратора. Использование указателя на функцию как параметр std::sort не желателен, так как сравнение не встраивается (inline). lambda отлично встраивается. В вашей сортировке компилятор, думаю, встраивает сравнения:

                                    bool myfunction (int i,int j) { return (i<j); }
                                    ...
                                    t1=clock();
                                    // sort (A, A+N, myfunction ); => slower then next 2 lines by 1.7x
                                    // sort (A, A+N, []( int i, int j) { return i<j; } );
                                    sort (A, A+N );
                                    t2=clock();


                                    Времена (Visual Studio 2010, Release). std::sort быстрее примерно процентов на 10 (не важно с lambda или без):
                                    N=195312
                                    result: Ok, ncmp=0, time=28
                                    std::sort: Ok, ncmp=0, time=24
                                    std::sort (slow, no inlining): Ok, ncmp=0, time=41

                                    N=3124995
                                    result: Ok, ncmp=0, time=556
                                    std::sort: Ok, ncmp=0, time=489
                                    std::sort (slow, no inlining): Ok, ncmp=0, time=894

                                    N=99999847
                                    result: Ok, ncmp=0, time=21389
                                    std::sort: Ok, ncmp=0, time=19002
                                    std::sort (slow, no inlining): Ok, ncmp=0, time=32529
                                    • +2
                                      Заметил, что, если использовать для сравнения макрос iGT(a,b) (*(a)>*(b)), то ваша сортировка идёт вровень с std::sort. Мне кажется, что это очень достойный результат с учётом того, что std::sort использует другую сортировку на малых размерах и, возможно, ещё какие-нибудь оптимизации.
                                      • 0
                                        Спасибо. И я думаю, что std::sort писали больше, чем полдня.
                                      • 0
                                        Я попробовал наоборот:
                                        — добавил в свой код функциональный объект;
                                        — тоже применил std::sort к массиву.

                                        Получилось:

                                        N=195312
                                        mmsort: Ok, time=16
                                        std::sort: Ok, time=15



                                        N=3124995
                                        mmsort: Ok, time=422
                                        std::sort: Ok, time=437



                                        N=49999923
                                        mmsort: Ok, time=7738
                                        std::sort: Ok, time=8456
                                        N=99999847
                                        mmsort: Ok, time=16551
                                        std::sort: Ok, time=17455

                                        std::sort медленнее процентов на 5. Возможно, повлияло то, что все функции, кроме msort, при переделке получились inline.
                                      • 0
                                        На типе double мой алгоритм проиграл вчистую — std::sort там в 1.3 раза быстрее :(
                                        • 0
                                          Рискну предположить, что производительность msort сильно зависит от соотношения стоимостей операции swap и операции сравнения. Видимо он делает меньше сравнений, но больше перестановок.

                                          То есть, std::string — благоприятный тип: дешёвый предсказуемый swap, сравнение дороже
                                          А вот int[100] будет неудобен: swap — дорогой, а сравнение дешёвое.
                                          • 0
                                            Похоже. Если в qsort основной цикл — «сравниваем и иногда меняем», то в msort — либо «сравниваем и меняем всегда», либо «меняем целые блоки, не смотря ни на что».
                                        • 0
                                          >Сортируем буфер обмена: в нем были и остались R младших элементов массива
                                          Почему это? Это же неправда, взять хотя бы тест 1 2 3 4 5 -5 -4 -3 -2 -1
                                          • 0
                                            Разумеется. В предыдущем пункте («Ищем на стыке предыдущего и следующего пунктов ошибку в алгоритме...») и в самом конце статьи как раз об этом и говорится :)
                                            • 0
                                              Вообще-то в тесте нет одинаковых элементов
                                              • 0
                                                «А что же за ошибка была в описании алгоритма? Дело в том, что если в буфер обмена или в остаток попал элемент, который после сортировки должен находиться в одной из первых R позиций, то в итоге он на место никак не попадет...»
                                                Или Ваш пример не попадает в этот случай?
                                                • 0
                                                  Теперь всё ясно, я просто подумал, что конец статьи — это то, что после «UPD:». Большое спасибо.
                                          • 0
                                            Вам может быть интересно: github.com/BonzaiThePenguin/WikiSort (идея та же самая)

                                            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.