В чем разница merge sort и quick sort и их преимущества
Что проверяют
Понимаете ли вы, чем алгоритмы отличаются по гарантиям, а не только по формуле O(n log n). Для Java-разработчика почти всегда следует уточнение: какой алгоритм стоит внутри Arrays.sort и Collections.sort и почему они разные.
Как отвечать
Оба алгоритма работают по принципу «разделяй и властвуй», но основную работу делают в разных местах. Merge sort делит массив пополам, а трудится при слиянии. Quick sort трудится при разбиении вокруг опорного элемента, и склеивать потом ничего не нужно.
- сложность: у merge sort O(n log n) в любом случае. У quick sort O(n log n) в среднем и O(n²) в худшем, когда опорный элемент раз за разом оказывается минимумом или максимумом;
- память: merge sort на массиве требует O(n) под буфер слияния. Quick sort сортирует на месте, стек рекурсии O(log n), если сначала уходить в меньшую часть;
- стабильность: merge sort стабилен, равные элементы сохраняют исходный порядок. Классический quick sort нет;
- практика: quick sort обычно быстрее на массивах за счёт локальности кэша и меньших констант. Merge sort выигрывает на связных списках, где слияние не требует лишней памяти, и во внешней сортировке данных, не влезающих в память.
Дальше свяжите с JDK. Arrays.sort для примитивов использует Dual-Pivot Quicksort: стабильность для int смысла не имеет, а скорость важна. Для объектов Arrays.sort(Object[]), Collections.sort и List.sort используют TimSort, гибрид слияния и вставок. Стабильность здесь нужна, чтобы сортировка по второму полю не ломала порядок по первому, а на уже упорядоченных кусках TimSort близок к линейному времени.
Где спотыкаются
Говорят, что quick sort всегда деградирует на отсортированном массиве. Это верно только для наивного выбора опорного элемента, первого или последнего. Медиана трёх или случайный pivot эту ловушку снимают.
Считают, что quick sort расходует O(1) памяти. Стек рекурсии никуда не девается, и если не уходить сначала в меньшую часть, в худшем случае он дорастает до O(n).
Не могут объяснить, почему в JDK два разных алгоритма. Ответ «так исторически сложилось» слабый: дело в стабильности для объектов и в скорости для примитивов.