Зачем использовать два разных алгоритма для сортировки массивов?

Question

В классе Arrays быстрая сортировка используется для сортировки примитивов, но для сортировки объектов это сортировка слиянием.

Интересно, почему это так?

Answer 1

Причиной использования сортировки слиянием является то, что им нужен стабильный алгоритм - например, где равные объекты (по compareTo() или compare()) находятся в том же относительном порядке, что и раньше.

Для примитивов равенство подразумевает «неразличимость». При сортировке от {5, 3, 5} до {3, 5, 5} не имеет значения, какая из пятерок была первой раньше. Таким образом, мы можем использовать более быстрый (и нестабильный) алгоритм быстрой сортировки здесь.

Answer 2

Просто предположение, но быстрая сортировка в худшем случае - O (n ^ 2), а сортировка слиянием стабильна (гарантировано O (n log n)).

Наихудший случай быстрой сортировки инициируется равными значениями .. и равные примитивы идентичны, тогда как "равные" объекты могут не быть.