which is the best sorting algorithm for a large array ?? asked 22 Jan '13, 23:39

Any algorithm that promises n * log(n) time and uses less extra space is good . Merge sort is one example which takes the minimum asymptotic time i.e. n * log(n) and takes O(n) space . NOTE : It is a proven fact that a sorting algorithm cannot take less than n * log(n) time if the array contains arbitrary entries . If the array entries come from a limited set then algorithms like counting sort can sort the array in order n time . answered 22 Jan '13, 23:44
Thanks Vineet....
(23 Jan '13, 00:13)
I just discovered this post and I would like to clarify one thing. @vineetpaliwal is almost correct. Comparisonbased sorting algorithms cannot be faster than NlgN. However, sorts like Radix Sort can be O(N).
(10 Mar '13, 05:48)

check out this http://bigocheatsheet.com/#sorting you will get the answer :) enjoy :) answered 25 May '13, 17:20
1
I personally think that merge sort is the best sorting algorithm....
(26 May '13, 13:22)
yup! its little bit slower than quick sort but it is stable algorithm :)
(26 May '13, 13:28)

Hello @praveen_kishor, This problem: can somehow be used as a "benchmark" for how fast a sorting algorithm needs to be in order to solve sorting related problems here. My advice is that you experiment different algorithms and also explore the builtin sorting functions on the language you are using... That should help you to answer this question. Best regards, Bruno answered 22 Jan '13, 23:45

Try using stl functions like sort. You'll need to to use a vector for that. Once you have a vector say "vec" with values contained in it, you can sort it with the function sort(vec.begin(),vec.end()). This will sort the entire array. Refer to this link and you may get a better idea. http://www.cplusplus.com/reference/algorithm/sort/ answered 23 Jan '13, 00:38
Thanks ani, but stl functions are only for c++ ( as i know ). What if i want to write sorting programs in C ?
(23 Jan '13, 00:54)
1
Then you can use function qsort() from stdlib.h:
(23 Jan '13, 01:02)
Yes, stl exists only for c++ . But, you can have a look at the sorting techniques running in nlogn here : http://en.wikipedia.org/wiki/Sorting_algorithm . I think merge sort and heap sort are good options. Try implementing the mergesort algorithm .
(23 Jan '13, 01:03)
1
@ani94 i would like to point out that its not necessary to use a vector for using sort function in c++. if u have an array of size n u can simply go for sort(a,a+n)
(23 Jan '13, 09:34)

I think merge sort is best algorithm for large array. It time complexity O(n log(n) at worst case and space complexity is O(n) at worst case. Merge sort is the clear winner in terms of speed. answered 12 Nov '16, 21:03

The best sorting algorithms work on the divide and conquer rule. if any algorithm has O(nlogn) complexity then it is considered good as there is no other sorting algorithm that gives complexity less than O(nlogn). Various sorting algorithms are
Conclusion : According to me Randomised Quick sort is the best sorting algorithm. answered 10 Apr '17, 23:06
