Quick sort и merge sort
| Свойство | Quick sort | Merge sort |
|---|---|---|
| Среднее время | O(n log n) | O(n log n) |
| Худшее время | O(n²) | O(n log n) |
| Доп. память для массива | partition in-place + stack | O(n) buffer + stack |
| Стабильность | обычно нет | да при корректном merge |
| Локальность в массиве | обычно хорошая | последовательное чтение/запись, но копирование |
| Linked list | неестественен | удобен |
Quicksort часто быстр на массивах благодаря in-place partition и локальности, но результат зависит от pivot и обработки дубликатов. Merge sort выбирают, когда важны стабильность и гарантированное O(n log n), либо данные удобно читать последовательными сериями.
Для внешней сортировки, когда данные не помещаются в RAM, merge-подход естественен: отсортировать помещающиеся chunks, записать их и выполнить k-way merge.
В стандартной библиотеке выбор реализации зависит от типа данных и версии JDK; на собеседовании лучше обсуждать свойства алгоритмов, а не запоминать одну внутреннюю реализацию навсегда.
На собеседовании
- Какой алгоритм гарантирует O(n log n)? Merge sort.
- Какой требует O(n) буфер для массива? Merge sort.
- Почему стабильность важна? Сохраняет предыдущий порядок равных ключей при многокритериальной сортировке.
- Что выбрать для external sort? Merge sort/k-way merge.