Самый эффективный способ сортировки arrya

Question

Каков наиболее эффективный способ сортировки массива на любом языке? С наименьшими значениями O() и P(). Я считаю, что сортировка оболочки является одним из лучших способов сортировки, но есть ли что-то более быстрое?

Answer 1

Чтобы сделать его коротким:

Introsort и Timsort являются наиболее часто используемые алгоритмы сортировки в реальном мире.

В среднем они имеют как O (nlogn) сложность, так и в худших случаях, что делает их лучше, чем QuickSort в тех случаях, когда Quicksort находится в O (n^2). Introsort используется в C и C++ STL, а Timsort используется в реализациях Python и Java (по крайней мере для сортировки массивов объектов в Java).

Оболочка Shell находится в O (n (logn)^2), поэтому немного медленнее, но использует меньше памяти, поэтому может быть пригодна для встроенных систем. См. enter link description here для получения более подробной информации.