Чтобы ответить на оригинальный вопрос и обратиться к некоторым другим комментариям здесь:
Я просто сравнил реализации выбора, быстрого, слияния и сортировки кучи, чтобы увидеть, как они складываются друг с другом. Ответ в том, что у всех есть свои недостатки.
TL; DR:
Быстрый - лучший вид общего назначения (достаточно быстрый, стабильный и в основном на месте)
Лично я предпочитаю сортировку в куче, если только мне не нужна стабильная сортировка.
Выбор - N ^ 2 - Это действительно хорошо только для менее чем 20 элементов или около того, тогда оно превосходит. Если ваши данные уже не отсортированы, или очень, очень почти так. N ^ 2 становится очень медленным, очень быстрым.
Быстрый, по моему опыту, на самом деле не такой быстрый . Бонусы за использование быстрой сортировки в качестве общей сортировки заключаются в том, что она достаточно быстрая и стабильная. Это также алгоритм на месте, но, поскольку он обычно реализуется рекурсивно, он займет дополнительное место в стеке. Он также находится где-то между O (n log n) и O (n ^ 2). Сроки для некоторых сортов, кажется, подтверждают это, особенно когда значения находятся в узком диапазоне. Это намного быстрее, чем сортировка выделения на 1000000 элементов, но медленнее, чем слияние или куча.
Сортировка слиянием гарантируется O (n log n), поскольку ее сортировка не зависит от данных. Он просто делает то, что делает, независимо от того, какие значения вы ему дали. Это также стабильно, но очень большие сортировки могут взорвать ваш стек, если вы не будете осторожны с реализацией. Существуют некоторые сложные реализации сортировки слиянием на месте, но, как правило, вам нужен еще один массив на каждом уровне для объединения ваших значений. Если эти массивы живут в стеке, вы можете столкнуться с проблемами.
Сортировка кучи - max O (n log n), но во многих случаях это происходит быстрее, в зависимости от того, как далеко вы должны переместить свои значения вверх по log n глубокой куче. Куча может быть легко реализована на месте в исходном массиве, поэтому ей не требуется дополнительная память, и она итеративна, поэтому не стоит беспокоиться о переполнении стека во время повторения. Огромный недостаток в сортировке кучи состоит в том, что она не является стабильной сортировкой, а это значит, что она нужна, если вам это нужно.