Блог

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

Есть ли какая-либо причина, по которой будет использоваться сортировка слиянием сверху вниз и почему это было бы предпочтительнее / проще реализовать, чем сортировка слиянием снизу вверх?

Предполагая, что обе являются оптимизированными и базовыми (не гибридными) версиями сортировки слиянием, возникает вопрос, если размер массива не равен степени 2, то top down выполняет лучшее разделение, но top down не начинает никакого объединения до тех пор, пока рекурсивное разделение не произведет два прогона размером 1, поэтому выигрыша нет, а дисбаланс в размере подмассивов влияет на общую производительность не так сильно, как накладные расходы на рекурсивное разделение массива и сохранение всех этих индексов в стеке. Также возникает вопрос о местоположении кэша: при сортировке слиянием сверху вниз, когда размер подмассива достаточно мал, объединенные (выходные) данные все еще будут в кэше и доступны в качестве входных данных для следующей операции слияния, но в то же время к этому кешу объединенных данных также осуществляется доступ для сброса их в основную память.

Затраты времени на рекурсию сверху вниз имеют временную сложность O (log2 (n)), в то время как общая временная сложность сортировки как для сортировки слиянием сверху вниз, так и для сортировки слиянием снизу вверх составляет O (n log2 (n)), поэтому по мере увеличения размера массива относительные затраты сверху вниз уменьшаются, поскольку большая часть времени будет потрачена на объединение подмассивов.

Во всех моих контрольных тестах сортировка снизу вверх всегда выполняется быстрее, чем сверху вниз, но на относительно небольшую величину для больших массивов. В моей системе (Intel 3770K 3,5 ГГц, 64-разрядная версия Windows 7 Pro, Visual Studio 2015) для 16 миллионов 64-разрядных целых чисел без знака снизу вверх требуется около 1,5 секунды, сверху вниз — около 1,6 секунды.

Большинство реальных библиотек используют некоторую разновидность сортировки слиянием снизу вверх, обычно гибридную комбинацию сортировки вставкой для небольших подмассивов (от 16 до 64 элементов) и сортировки слиянием снизу вверх, такую как TimSort. Размер подмассива, используемого при сортировке по вставке, выбирается таким образом, чтобы для сортировки по вставке требовалось четное число проходов, при этом отсортированные данные заканчивались в исходном массиве.

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