Вступление

Эта статья описывает стабильный нерекурсивный адаптивный алгоритм сортировки слиянием под названием quadsort.

Четверной обмен

В основе quadsort лежит четверной обмен. Традиционно большинство алгоритмов сортировки разработаны на основе бинарного обмена, где две переменные сортируются с помощью третьей временной переменной. Обычно это выглядит следующим образом:

    if (val[0] > val[1])    {        tmp[0] = val[0];        val[0] = val[1];        val[1] = tmp[0];    }

В четверном обмене происходит сортировка с помощью четырёх подменных переменных (своп). На первом этапе четыре переменные частично сортируются в четыре своп-переменные, на втором этапе они полностью сортируются обратно в четыре исходные переменные.

                                         A         S?    F                                   ?                     ?                                  A         S         F                                                                                ?F   ?F                                                                  A         S         F                                    ?                        ?                               A         S?    F                                         

Этот процесс показан на диаграмме выше.

После первого раунда сортировки одна проверка if определяет, отсортированы ли четыре своп-переменные по порядку. Если это так, то обмен завершается немедленно. Затем проверяется, отсортированы ли своп-переменные в обратном порядке. Если это так, то сортировка завершается немедленно. Если обе проверки дают отрицательный результат, то окончательное расположение известно и остаются две проверки для определения окончательного порядка.

Это исключает одно лишнее сравнение для последовательностей, который располагаются по порядку. В то же время создаётся одно дополнительное сравнение для случайных последовательностей. Однако в реальном мире мы редко сравниваем действительно случайные данные. Поэтому когда данные скорее упорядочены, чем беспорядочны, этот сдвиг в вероятности даёт преимущество.

Существует также общее повышение производительности за счёт исключения расточительного свопа. На языке C базовый четверной своп выглядит следующим образом:

    if (val[0] > val[1])    {        tmp[0] = val[1];        tmp[1] = val[0];    }    else    {        tmp[0] = val[0];        tmp[1] = val[1];    }    if (val[2] > val[3])    {        tmp[2] = val[3];        tmp[3] = val[2];    }    else    {        tmp[2] = val[2];        tmp[3] = val[3];    }    if (tmp[1] <= tmp[2])    {        val[0] = tmp[0];        val[1] = tmp[1];        val[2] = tmp[2];        val[3] = tmp[3];    }    else if (tmp[0] > tmp[3])    {        val[0] = tmp[2];        val[1] = tmp[3];        val[2] = tmp[0];        val[3] = tmp[1];    }    else    {       if (tmp[0] <= tmp[2])       {           val[0] = tmp[0];           val[1] = tmp[2];       }       else       {           val[0] = tmp[2];           val[1] = tmp[0];       }       if (tmp[1] <= tmp[3])       {           val[2] = tmp[1];           val[3] = tmp[3];       }       else       {           val[2] = tmp[3];           val[3] = tmp[1];       }    }

В случае, если массив не может быть идеально разделён на четыре части, хвост из 1-3 элементов сортируется с помощью традиционного бинарного обмена.

Описанный выше четверной обмен реализован в quadsort.

Четверное слияние

На первом этапе четверной обмен предварительно сортирует массив на четырёхэлементные блоки, как описано выше.

На втором этапе используется похожий подход для обнаружения упорядоченных и обратных порядков, но в блоках по 4, 16, 64 или более элементов этот этап обрабатывается как традиционная сортировка слиянием.

Это можно представить следующим образом:

main memory: AAAA BBBB CCCC DDDDswap memory: ABABABAB  CDCDCDCDmain memory: ABCDABCDABCDABCD

В первой строке четверной обмен используется для создания четырёх блоков по четыре отсортированных элемента в каждом. Во второй строке используется четверное слияние для объединения в два блока по восемь отсортированных элементов каждый в своп-памяти. В последней строке блоки объединяются обратно в основную память, и мы остаемся с одни блоком из 16 отсортированных элементов. Ниже приводится визуализация.



Эти операции действительно требуют удвоения памяти для свопа. Подробнее об этом позже.

Пропуск

Ещё одно отличие заключается в том, что из-за возросшей стоимости операций слияния выгодно проверить, находятся ли четыре блока в прямом или обратном порядке.

В случае, если четыре блока упорядочены, операция слияния пропускается, так как является бессмысленной. Однако это требует дополнительной проверки if, и для случайно отсортированных данных эта проверка if становится всё более маловероятной по мере увеличения размера блока. К счастью, частота этой проверки if уменьшается вчетверо каждый цикл, в то время как потенциальная выгода каждый цикл увеличивается вчетверо.

В случае, если четыре блока находятся в обратном порядке, выполняется стабильный своп на месте.

В том случае, если только два из четырёх блоков упорядочены или находятся в обратном порядке, сравнения в самом слиянии излишни и впоследствии опускаются. Данные всё ещё нужно скопировать в своп-память, но это менее вычислительная процедура.

Это позволяет алгоритму quadsort сортировать последовательности в прямом и обратном порядке, используя n сравнений вместо n * log n сравнений.

Проверки границ

Ещё одна проблема с традиционной сортировкой слиянием заключается в том, что она тратит ресурсы на лишние проверки границ. Это выглядит следующим образом:

    while (a <= a_max && b <= b_max)        if (a <= b)            [insert a++]        else            [insert b++]

Для оптимизации наш алгоритм сравнивает последний элемент последовательности A с последним элементом последовательности B. Если последний элемент последовательности A меньше последнего элемента последовательности B, то мы знаем, что проверка b < b_max всегда будет ложной, потому что последовательность A первой полностью сливается.

Аналогично, если последний элемент последовательности A больше последнего элемента последовательности B, мы знаем, что проверка a < a_max всегда будет ложной. Это выглядит следующим образом:

    if (val[a_max] <= val[b_max])        while (a <= a_max)        {            while (a > b)                [insert b++]            [insert a++]        }    else        while (b <= b_max)        {            while (a <= b)                [insert a++]            [insert b++]        }

Слияние хвоста

При сортировке массива из 65 элементов вы в конечном итоге получаете сортированный массив из 64 элементов и сортированный массив из одного элемента в конце. Это не приведёт к дополнительной операции свопа (обмена), если вся последовательность в порядке. В любом случае, для этого программа должна выбрать оптимальный размер массива (64, 256 или 1024).

Другая проблема заключается в том, что неоптимальный размер массив приводит к лишним операциям обмена. Чтобы обойти эти две проблемы, процедура четверного слияния прерывается, когда размер блока достигает 1/8 размера массива, а остальная часть массива сортируется с помощью слияния хвоста. Основное преимущество слияния хвоста заключается в том, что оно позволяет сократить объём свопа quadsort до n/2 без существенного влияния на производительность.

Big O

Когда данные уже отсортированы или отсортированных в обратном порядке, quadsort совершает n сравнений.

Кэш

Поскольку quadsort использует n/2 объёма своп-памяти, использование кэша не так идеально, как сортировка на месте. Однако сортировка случайных данных на месте приводит к неоптимальному обмену. Основываясь на моих бенчмарках, quadsort всегда быстрее, чем сортировка на месте, если массив не переполняет кэш L1, который на современных процессорах может достигать 64КБ.

Wolfsort

Wolfsort это гибридный алгоритм сортировки radixsort/quadsort, который улучшает производительность при работе со случайными данными. Это в основном доказательство концепции, которое работает только с беззнаковыми 32-и 64-битными целыми числами.

Визуализация

В приведённой ниже визуализации выполняются четыре теста. Первый тест основан на случайном распределении, второй на распределении по возрастанию, третий на распределении по убыванию, четвёртый на распределении по возрастанию со случайным хвостом.

Верхняя половина показывает своп, а нижняя основную память. Цвета различаются для операций пропуска, свопа, слияния и копирования.

Бенчмарк: quadsort, std::stable_sort, timsort, pdqsort и wolfsort

Следующий бенчмарк был запущен на конфигурации WSL gcc версии 7.4.0 (Ubuntu 7.4.0-1ubuntu1~18.04.1). Исходный код скомпилирован командой g++ -O3 quadsort.cpp. Каждый тест выполнен сто раз, и сообщается только о лучшем запуске.

По оси абсцисс время выполнения.




Следует отметить, что pdqsort не является стабильной сортировкой, поэтому он быстрее работает с данными в обычном порядке (общий порядок).

Следующий бенчмарк запускался на WSL gcc версии 7.4.0 (Ubuntu 7.4.0-1ubuntu1~18.04.1). Исходный код скомпилирован командой g++ -O3 quadsort.cpp. Каждый тест выполнен сто раз, и сообщается только о лучшем запуске. Он измеряет производительность на массивах размером от 675 до 100000 элементов.

Ось X приведённого ниже графика это количество элементов, ось Y время выполнения.

Бенчмарк: quadsort и qsort (mergesort)

Следующий бенчмарк запускался на WSL gcc версии 7.4.0 (Ubuntu 7.4.0-1ubuntu1~18.04.1). Исходный код скомпилирован командой g++ -O3 quadsort.cpp. Каждый тест выполнен сто раз, и сообщается только о лучшем запуске.

         quadsort: sorted 1000000 i32s in 0.119437 seconds. MO:   19308657 (случайный порядок)            qsort: sorted 1000000 i32s in 0.133077 seconds. MO:   21083741 (случайный порядок)         quadsort: sorted 1000000 i32s in 0.002071 seconds. MO:     999999 (возрастание)            qsort: sorted 1000000 i32s in 0.007265 seconds. MO:    3000004 (возрастание)         quadsort: sorted 1000000 i32s in 0.019239 seconds. MO:    4007580 (возрастание ступенями)            qsort: sorted 1000000 i32s in 0.071322 seconds. MO:   20665677 (возрастание ступенями)         quadsort: sorted 1000000 i32s in 0.076605 seconds. MO:   19242642 (общий порядок)            qsort: sorted 1000000 i32s in 0.038389 seconds. MO:    6221917 (общий порядок)         quadsort: sorted 1000000 i32s in 0.002305 seconds. MO:     999999 (убывание)            qsort: sorted 1000000 i32s in 0.009659 seconds. MO:    4000015 (убывание)         quadsort: sorted 1000000 i32s in 0.022940 seconds. MO:    9519209 (убывание ступенями)            qsort: sorted 1000000 i32s in 0.042135 seconds. MO:   13152042 (убывание ступенями)         quadsort: sorted 1000000 i32s in 0.034456 seconds. MO:    6787656 (случайный хвост)            qsort: sorted 1000000 i32s in 0.098691 seconds. MO:   20584424 (случайный хвост)         quadsort: sorted 1000000 i32s in 0.066240 seconds. MO:   11383441 (случайная половина)            qsort: sorted 1000000 i32s in 0.118086 seconds. MO:   20572142 (случайная половина)         quadsort: sorted 1000000 i32s in 0.038116 seconds. MO:   15328606 (распределение волнами)            qsort: sorted 1000000 i32s in 4.471858 seconds. MO: 1974047339 (распределение волнами)         quadsort: sorted 1000000 i32s in 0.060989 seconds. MO:   15328606 (стабильный)            qsort: sorted 1000000 i32s in 0.043175 seconds. MO:   10333679 (нестабильный)         quadsort: sorted    1023 i32s in 0.016126 seconds.       (random 1-1023)            qsort: sorted    1023 i32s in 0.033132 seconds.       (random 1-1023)

Показатель MO указывает количество сравнений, выполненных для 1 миллиона элементов.

В приведённом выше бенчмарке quadsort сравнивается с glibc qsort() через тот же интерфейс общего назначения и без каких-либо известных несправедливых преимуществ, таких как инлайнинг.

     random order: 635, 202,  47, 229, etc  ascending order: 1, 2, 3, 4, etc    uniform order: 1, 1, 1, 1, etc descending order: 999, 998, 997, 996, etc       wave order: 100, 1, 102, 2, 103, 3, etc  stable/unstable: 100, 1, 102, 1, 103, 1, etc     random range: time to sort 1000 arrays ranging from size 0 to 999 containing random data

Бенчмарк: quadsort и qsort (quicksort)

Этот конкретный тест выполнен с использованием реализации qsort() от Cygwin, которая под капотом использует quicksort. Исходный код скомпилирован командой gcc -O3 quadsort.c. Каждый тест выполнен сто раз, сообщается только о лучшем запуске.

         quadsort: sorted 1000000 i32s in 0.119437 seconds. MO:   19308657 (случайный порядок)            qsort: sorted 1000000 i32s in 0.133077 seconds. MO:   21083741 (случайный порядок)         quadsort: sorted 1000000 i32s in 0.002071 seconds. MO:     999999 (возрастание)            qsort: sorted 1000000 i32s in 0.007265 seconds. MO:    3000004 (возрастание)         quadsort: sorted 1000000 i32s in 0.019239 seconds. MO:    4007580 (возрастание ступенями)            qsort: sorted 1000000 i32s in 0.071322 seconds. MO:   20665677 (возрастание ступенями)         quadsort: sorted 1000000 i32s in 0.076605 seconds. MO:   19242642 (общий порядок)            qsort: sorted 1000000 i32s in 0.038389 seconds. MO:    6221917 (общий порядок)         quadsort: sorted 1000000 i32s in 0.002305 seconds. MO:     999999 (убывание)            qsort: sorted 1000000 i32s in 0.009659 seconds. MO:    4000015 (убывание)         quadsort: sorted 1000000 i32s in 0.022940 seconds. MO:    9519209 (убывание ступенями)            qsort: sorted 1000000 i32s in 0.042135 seconds. MO:   13152042 (убывание ступенями)         quadsort: sorted 1000000 i32s in 0.034456 seconds. MO:    6787656 (случайный хвост)            qsort: sorted 1000000 i32s in 0.098691 seconds. MO:   20584424 (случайный хвост)         quadsort: sorted 1000000 i32s in 0.066240 seconds. MO:   11383441 (случайная половина)            qsort: sorted 1000000 i32s in 0.118086 seconds. MO:   20572142 (случайная половина)         quadsort: sorted 1000000 i32s in 0.038116 seconds. MO:   15328606 (распределение волнами)            qsort: sorted 1000000 i32s in 4.471858 seconds. MO: 1974047339 (распределение волнами)         quadsort: sorted 1000000 i32s in 0.060989 seconds. MO:   15328606 (стабильный)            qsort: sorted 1000000 i32s in 0.043175 seconds. MO:   10333679 (нестабильный)         quadsort: sorted    1023 i32s in 0.016126 seconds.       (random 1-1023)            qsort: sorted    1023 i32s in 0.033132 seconds.       (random 1-1023)

В этом бенчмарке становится ясно, почему quicksort часто предпочтительнее традиционного слияния, он делает меньше сравнений для данных в возрастающем порядке, равномерно распределённых и для данных в убывающем порядке. Однако в большинстве тестов он показал себя хуже, чем quadsort. Quicksort также демонстрирует чрезвычайно низкую скорость сортировки данных, упорядоченных волнами. Тест с данными в случайном порядке показывает, что quadsort более чем в два раза быстрее при сортировке небольших массивов.

Quicksort быстрее в универсальных и стабильных тестах, но только потому, что это нестабильный алгоритм.