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.

For example (excluding some sorting techniques already mentioned in other answers),

  • Pigeonhole sort and counting sort are two non comparison-based sorting techniques, that is extremely fast, when the range of the keys is small enough.
  • For sorting keys that are strings (or string-like) of lengths very small compared to number of items to be sorted, radix sort is fast. But, as the length of the largest (or, average, let us say) key increases, this technique might not be a good choice.

You said only best sorting technique. The question does not say what “best” means. So I am taking the liberty to extend the meaning, not only to include time complexity, but a few other factors.

  • Cycle sort is a sorting technique that makes the theoretically optimal number of writes in the original array. Useful in applications that use such memory, where lots of writing can degrade (like reducing the lifetime) the memory.
  • Bubble sort is known for its tiny code size. Storing the program is efficient here.
  • Merge sort is a highly parallelizable sorting algorithm, which makes it extremely useful in case of processing very large data sets with possible parallelization.

What I(and others) am(are) trying to say here is that, there is no “best” sorting algorithm in general. There are better ones suited for particular situations. So, choose the best one for a particular situation.

2 Likes
//