Предполагая, что обе являются оптимизированной и базовой (не гибридной) версиями сортировки слиянием, возникает вопрос, если размер массива не равен степени 2, то сверху вниз лучше разбивать, но сверху вниз не начинается слияние до тех пор, пока рекурсивное разбиение не приведет к двум прогонам размера 1, поэтому никакого усиления нет, и дисбаланс в размере подмассивов не влияет на общую производительность в той же степени, что и затраты на рекурсивное разбиение массива и сохранение всех этих индексов в стек. Существует также вопрос о расположении кэша: для сортировки слиянием сверху вниз, когда размер подмассива достаточно мал, объединенные (выходные) данные все еще будут находиться в кэше и будут доступны в качестве входных данных для следующей операции слияния, но в то же время Доступ к кэшу объединенных данных также доступен для его выгрузки в основную память.
Затраты на рекурсию для сверху вниз имеют сложность времени O (log2 (n)), в то время как общая сложность времени сортировки для сортировки слиянием сверху вниз и снизу вверх составляет O (n log2 (n)), так что массив размер становится больше, относительные накладные расходы сверху вниз уменьшаются, так как большую часть времени будет потрачено на слияние подмассивов.
Во всех моих тестах производительности восходящее значение всегда быстрее, чем сверху вниз, но для больших массивов оно относительно небольшое. В моей системе (Intel 3770K 3,5 ГГц, Windows 7 Pro 64 bit, Visual Studio 2015), для 16 миллионов 64-битных целых чисел без знака, восходящее время занимает около 1,5 секунды, сверху вниз около 1,6 секунды.
В большинстве современных библиотек используется некоторая разновидность сортировки по принципу «снизу вверх», обычно это гибридная комбинация сортировки вставкой для небольших подмассивов (от 16 до 64 элементов) и сортировки «снизу вверх», такой как TimSort. Размер подмассива для использования с сортировкой вставки выбирается таким образом, чтобы он занимал четное число проходов сортировки слиянием, а отсортированные данные заканчиваются в исходном массиве.
Это делает сортировку слиянием сверху вниз в основном учебным упражнением, особенно если его обучают вместе с быстрой сортировкой, которая также сверху вниз.