 # Best Sorting algorithm

Which algorithm is the Best one to Sort…
Could somebody explain it with best and worst cases…

For large inputs, Mergesort, Heapsort and Quicksort are the best algorithms with worst case running time of Mergesort and Heapsort, and the average case running time of Quicksort being O(nlogn).(The worst case of Quicksort which has a running time of O(n^2), occurs very rarely and can be avoided by a good pivot choosing algorithm but it is not guaranteed that worst case won’t occur).

While for short inputs, Insertion sort runs best with best case running time O(n) and worst case running time O(n^2).

If you dont know these algorithms then I would recommend you to go through CLRS to learn these algorithms in detail. A good visual explanation of all these algos is given on this

Most of the library sorting functions use Introsort for sorting which uses all the three heapsort, quicksort and insertion sort to give optimal run time performance.

1 Like

For Merge sort worst case is O(nlog(n)), for Quick sort: O(n2). For other cases (avg, best) both have O(nlog(n)). However Quick sort is space constant where Merge sort depends on the structure you’re sorting.

1 Like

Also you can use CountingSort with complexity O(N + max_value) and RadixSort with complexity O(N*d), d=number of digits.

2 Likes

The choice of the best sorting algorithm depends on the context.

Each sorting algorithm has its own advantages than any other one, in its own unique setup.