Эффективные сортировки работают за O(n log n) — это намного быстрее O(n²) на больших данных. Две классические основаны на принципе «разделяй и властвуй»:
Сортировка слиянием (merge sort) делит массив пополам, сортирует половины рекурсивно, затем сливает их в один отсортированный. Стабильна и предсказуема — всегда O(n log n).
Быстрая сортировка (quick sort) выбирает опорный элемент, делит массив на меньшие и большие, рекурсивно сортирует части. В среднем O(n log n), очень быстра на практике.
Хорошая новость: писать их руками в реальной работе не нужно — эффективные сортировки уже встроены в языки:
[3, 1, 2].sort((a, b) => a - b) // JavaScript sorted([3, 1, 2]) // Python
Важно понимать стоимость: сортировка — это O(n log n), и если вы сортируете внутри цикла, общая сложность растёт. Знать сложность встроенных операций важнее, чем уметь писать сортировку с нуля.