Mergesort - это антипод Quicksort'а: во время разбиения на части мы не смотрим на ключи, делим совершенно произвольно на две примерно одинаковые части, сортируем их рекурсивно, а потом нужна процедура слияния - два отсортированных массива (множества элементов которых могут крепко пересекаться) нужно "слить" в один. Это линейная операция. Суммарно тот же O(n log n).
Раньше, сравнивая Quicksort и Mergesort, я считал, что они асимптотически одинаковы для среднего случая (O(n log n)), Mergesort лучше в худшем случае (всё ещё O(n log n) vs O(n^2)), а Quicksort лучше на практике из-за хорошей локальности на нижних уровнях рекурсии.
Но мне никогда не приходило в голову, что Quicksort может быть именно асимптотически, фундаментально лучше Mergesort. Оказывается, может. Если сортировать большие объёмы данных на hadoop кластере из K машин, то с K-way Quicksort'ом можно получить время O(n/K log n/K). Если выбирать барьеры для сегментов при помощи случайной выборки, то ни на одном этапе не нужен будет линейный проход массива. Mergesort approach, как ни крути, потребует в самом конце reducer, который всё "сольёт", т.е. на одном хосте прочешет весь массив. Получаем плохой O(n), вне зависимости от K.
Однако.
