 # best way to sort an array

pleas can anyone tell me best way to sort an array…also explain its algorithm and its working.
best way means least complexity.

1 Like

In terms of Complexity, the best algorithm is Counting or Bucket sort which runs in O(N) time. However it is not applicable in all situations and only when input follows specific constraints and also requires O(N) memory.These algorithms are not based on Comparison between numbers.

The best general sorting algorithms are Comparison based algorithms which run in at best O(N logN) time.Merge sort runs in worst case O(N logN) time but it requires O(N) extra memory. Heap Sort runs in O(N logN ) worst case time and requires only constant extra storage. Quick Sort runs in worst case O(n^2) time however it can be made to run in O(N) average time using randomization. The advantage of Quick sort is that it requires no extra memory (can run in place) and it outperforms other N logN algorithms in practical cases.

Most languages have inbuilt libraries with sorting algorithms.In C++ algorithm library ,you can use sort(arr,arr+n) where n is size of array.In Python you can use arr.sort() to sort an array.

I have not given detailed explanation about each algorithm as there is a lot of detailed material online.Based on your input and requirements of the problem you can decide which algorithm to choose.Here is the Wikipedia page for further reading

9 Likes

I think Heapsort and Mergesort are well known sorting algorithms with O(nlogn) complexity.
but Mergesort uses more memory.
Here is my blog post on Mergesort .Both Algorithm and Complexity are explained in detail Heap sort is in-place right? Its memory complexity is O(1) and not O(N).

1 Like

Thank you. My bad

1 Like