Fastest sorting algorithm .

general
1

Which is the fastest sorting algorithm?

1 Like
2

Inbuilt function of sort available in “algorithm” header file of C/C++… sort() are much faster than any other implemented sort!!

3 Likes
3

Merge Sort is the fastest stable sorting algorithm with worst-case complexity of O(nlogn), but it requires extra space. Although, if memory constraints are very tight you can use Quick Sort, whose worst-time compelxity is O(n^{2}) but average case complexity is O(nlogn).

A sorting algorithm is stable if whenever there are two records R and S with the same key, and R appears before S in the original list, then R will always appear before S in the sorted list.

If you feel your question has been answered, mark it as accepted.

1 Like
4

Refer this link

1 Like
5

I think quick sort is faster than merge sort(don’t require much memory,and simpler operation in the inner loop). But i must say std::sort is the best sort and doesn’t require effort to code the algorithm.

2 Likes
6

This is a good link for time complexity of various algorithms and data structures.

http://bigocheatsheet.com/

1 Like
7

1)Merge Sort is unarguably the fastest sorting algorithm with a worst-case complexity= O(n logn) . This means that whatever be the arrangement of the elements in the array, it won’t take more than n*logn steps to sort the array. A standard computer generally takes 1 second to perform 10^8 such steps/operations. An important point to note here is that the base of the logarithm is 2 and not 10 or e as generally taken in schools. The only disadvantage of Merge Sort is that it requires extra space , i.e. an extra array to merge the sorted elements into. This is important to know because sometimes additional space has a great cost attached with it.

2)Quicksort is usually the sorting algorithm that is used everywhere. A few examples of this would be the inbuilt java, C++ sorting functions, MS Excel ,etc. Quicksort has an average worst-case complexity of O(n logn) but a worst-case complexity of O(n^2). However, this only occurs when the array is already sorted and can be overcome by randomizing the position of the pivot everytime. This is a very convenient technique since it does not have the additional cost of an entire new array.

1 Like
8

For competitive programming purposes, the standard library sort() should do just fine. In C++ it is an implementation of introsort.
Mergesort is often not a great candidate because of all the extra memory used.

On a side note, there is a sorting algorithm, block sort, that:

  • Uses O(1) extra memory
  • Is stable
  • Runs in O(N log N) in worst case
  • Runs in O(N) in best case
3 Likes
9

I use sorted().This is built-in in Python and is over 4 times faster than other sorting techniques.

1 Like
10

I think that a.sort() and sorted(a) have the same time complexity. Both use Tim Sort and I don’t it’s like 4 times faster or anything like that but it has a best case time complexity of O(n).

11

in java Arrays.sort(arr_name);

12

Well there’s no de facto 'fastest sorting algorithm (Else there’d be just one sorting algorithm and everybody would’ve used that). It all depends on how the input data is.

  • If the array is nearly sorted, then Insertion sort, Selection sort would be the algorithm of my choice.
  • If I already know the input elements range, eg. If I want to sort 1 billion characters, I know there’re just 26 unique elements, I’d go with Counting sort
  • If I’m sorting objects, I want the sort to be stable. I’d use Java’s Collections.sort() which internally uses Tim Sort
  • If I’m just sorting random numbers of which I have no data about(eg. range), I’d use Java’s Arrays.sort() which uses Double Pivoted Quick sort
1 Like
13

fastest sorting algorithm will be the merge sort.since the time complexity is less even in the worst case(nlogn).Even if the array is properly arranged or not,it wouldn’t take more than nlogn steps to sort the array.

14

C++ STL sort function is fastest. If you want your own implementation then randomized quick sort and heap sort are really good candidates as they are universal unlike radix sort which is O(n) but demands keys in lexicographic order.

Thus, overall inbuilt sort functions are quite fast and are thus widely used

15

Dear, don’t take it in wrong way, but the Q was asked last year, and already answered. Even what you said about C++ stl is what bansal said in his accepted answer. I know you want to help, but I don’t think bumping these 3-4 month old thread would be that helpful (many OPs wont be around now, or even they are ,chances are they might have already found the answers). Just take care that you don’t bump to the extent that threads more closer to current affairs get neglected.

I hope I put my point across amicably.

16

I totally agree with you mate. Thanks