Сравни алгоритмы сортировки по идее, сложности и применению.

Алгоритмы сортировки различаются идеей, сложностью и применением: простые (O(n²)) — для маленьких данных, эффективные (O(n log n)) — для больших.

Простые (O(n²))

• Пузырьковая (Bubble) — многократно меняет соседние элементы местами. Проста, но медленна. Учебная.
• Вставками (Insertion) — вставляет каждый элемент в отсортированную часть. Хороша на почти отсортированных и малых данных.
• Выбором (Selection) — находит минимум и ставит в начало. Мало обменов, но всегда O(n²).

Эффективные (O(n log n))

• Быстрая (Quick sort) — «разделяй и властвуй» вокруг опорного элемента. В среднем O(n log n), в худшем O(n²). Быстра на практике, in-place.
• Слиянием (Merge sort) — делит пополам, сортирует и сливает. Стабильна, гарантированно O(n log n), но нужна доп. память O(n).
• Пирамидальная (Heap sort) — через кучу. O(n log n), in-place, нестабильна.

Особые

• Подсчётом (Counting)/поразрядная (Radix) — O(n) для целых в ограниченном диапазоне (без сравнений).

Как выбирать

• Маленькие/почти отсортированные → вставками.
• Общий случай, память важна → быстрая.
• Нужна стабильность/гарантия → слиянием.
• Целые в узком диапазоне → подсчётом/поразрядная.

Array.prototype.sort в V8 использует Timsort (гибрид merge + insertion), стабильный, O(n log n).

Коротко для собеседования

Простые сортировки (пузырёк, вставками, выбором) — O(n²), для малых данных. Эффективные (быстрая, слиянием, пирамидальная) — O(n log n). Merge стабильна, но требует памяти; quick быстра in-place. Встроенный sort — стабильный Timsort O(n log n).