55
$\begingroup$

I have come across many sorting algorithms during my high school studies. However, I never know which is the fastest (for a random array of integers). So my questions are:

  • Which is the fastest currently known sorting algorithm?
  • Theoretically, is it possible that there are even faster ones? So, what's the least complexity for sorting?
$\endgroup$
  • 7
    $\begingroup$ What do you mean by "fast"? What do you want to measure? $\endgroup$ – Raphael Dec 2 '13 at 18:49
  • 2
    $\begingroup$ What does "random array of integers" mean? Random with what distribution? uniform distribution? Gaussian? Depending on the distribution there may be better than $\mathcal{O}(n\log{n})$ expected running time algorithms. $\endgroup$ – Bakuriu Dec 2 '13 at 22:05
  • $\begingroup$ @gen Take a look at Radix sort. Correct implementation has O(n) complexity for Int32 for example. $\endgroup$ – this Dec 3 '13 at 3:31
  • $\begingroup$ Have a look at the sort benchmark $\endgroup$ – adrianN Dec 3 '13 at 9:37
  • 1
    $\begingroup$ @gen: In terms of $\Theta$ asymptotics? Then, it's easy: pick any of the $\Theta(n \log n)$ algorithms. Note that this might have nothing to do with (average) real-world performance. This may be a worthwhile read in this regard. $\endgroup$ – Raphael Dec 3 '13 at 22:05
42
$\begingroup$

In general terms, there are the $O(n^2)$ sorting algorithms, such as insertion sort, bubble sort, and selection sort, which you should typically use only in special circumstances; Quicksort, which is worst-case $O(n^2)$ but quite often $O(n\log n)$ with good constants and properties and which can be used as a general-purpose sorting procedure; the $O(n\log n)$ algorithms, like merge-sort and heap-sort, which are also good general-purpose sorting algorithms; and the $O(n)$, or linear, sorting algorithms for lists of integers, such as radix, bucket and counting sorts, which may be suitable depending on the nature of the integers in your lists.

If the elements in your list are such that all you know about them is the total order relationship between them, then optimal sorting algorithms will have complexity $\Omega(n\log n)$. This is a fairly cool result and one for which you should be able to easily find details online. The linear sorting algorithms exploit further information about the structure of elements to be sorted, rather than just the total order relationship among elements.

Even more generally, optimality of a sorting algorithm depends intimately upon the assumptions you can make about the kind of lists you're going to be sorting (as well as the machine model on which the algorithm will run, which can make even otherwise poor sorting algorithms the best choice; consider bubble sort on machines with a tape for storage). The stronger your assumptions, the more corners your algorithm can cut. Under very weak assumptions about how efficiently you can determine "sortedness" of a list, the optimal worst-case complexity can even be $\Omega(n!)$.

This answer deals only with complexities. Actual running times of implementations of algorithms will depend on a large number of factors which are hard to account for in a single answer.

$\endgroup$
  • $\begingroup$ I guess some of those $O$ should be $\Omega$? $\endgroup$ – Raphael Dec 2 '13 at 19:01
  • 1
    $\begingroup$ @Raphael Meh. I think most of them are $\Theta$ anyhow. I suppose the lower bound is probably better rendered $\Omega$. I'll change a couple of them that make the most sense. $\endgroup$ – Patrick87 Dec 2 '13 at 19:03
  • 7
    $\begingroup$ I vote @Raphael gets a $\Omega$ police hat :P $\endgroup$ – Realz Slaw Dec 2 '13 at 20:57
  • 2
    $\begingroup$ @RealzSlaw: I'd wear it proudly. :] $\endgroup$ – Raphael Dec 2 '13 at 21:44
  • 1
    $\begingroup$ @gen See stackoverflow.com/a/3274203 for some discussion. Basically, if individual records are huge, and it's not stored in a random-access way, and the amount of data is such that it must be done in-place, then bubble sort is the way to go. These circumstances are usually rare nowadays, but you may still encounter them. $\endgroup$ – Patrick87 Dec 3 '13 at 16:40
16
$\begingroup$

The answer, as is often the case for such questions, is "it depends". It depends upon things like (a) how large the integers are, (b) whether the input array contains integers in a random order or in a nearly-sorted order, (c) whether you need the sorting algorithm to be stable or not, as well as other factors, (d) whether the entire list of numbers fits in memory (in-memory sort vs external sort), and (e) the machine you run it on.

In practice, the sorting algorithm in your language's standard library will probably be pretty good (pretty close to optimal), if you need an in-memory sort. Therefore, in practice, just use whatever sort function is provided by the standard library, and measure running time. Only if you find that (i) sorting is a large fraction of the overall running time, and (ii) the running time is unacceptable, should you bother messing around with the sorting algorithm. If those two conditions do hold, then you can look at the specific aspects of your particular domain and experiment with other fast sorting algorithms.

But realistically, in practice, the sorting algorithm is rarely a major performance bottleneck.

$\endgroup$
9
$\begingroup$

Furthermore, answering your second question

Theoretically, is it possible that there are even faster ones?
So, what's the least complexity for sorting?

For general purpose sorting, the comparison-based sorting problem complexity is Ω(n log n). There are some algorithms that perform sorting in O(n), but they all rely on making assumptions about the input, and are not general purpose sorting algorithms.

Basically, complexity is given by the minimum number of comparisons needed for sorting the array (log n represents the maximum height of a binary decision tree built when comparing each element of the array).

You can find the formal proof for sorting complexity lower bound here:

$\endgroup$
  • 3
    $\begingroup$ This answer is not quite right. $\Omega(n \log n)$ is not a universal lower bound for sorting. That lower bound only applies to comparison-based sorts, i.e., sorting algorithms that use only comparisons. Some sorting algorithms are not comparison-based. The statement "There are some algorithms that perform sorting in O(n), but they all rely on making assumptions about the input, and are not general purpose sorting algorithms." might be a little misleading -- be careful. Radix-sort is a general-purpose sorting algorithm (assuming you are sorting fixed-width integers). $\endgroup$ – D.W. Dec 3 '13 at 16:50
  • $\begingroup$ Depends on what you mean by the sorting problem. General-purpose comparison-based sorts are not the only kind of sorting problems people have. $\endgroup$ – Patrick87 Dec 3 '13 at 16:55
  • 1
    $\begingroup$ That's true, of course. I should have been more specific, thanks for pointing it out. However, I was a bit curious on which other sorting approaches (not comparison-based) you were referring to; Radix Sort is exactly the kind of O(n) algorithm I was talking about - you have to 'assume' something about the input (fixed-width integers). In this sense, it is not a general-purpose sorting algorithm, right? $\endgroup$ – rla4 Dec 3 '13 at 17:04
  • 1
    $\begingroup$ @D.W.: Radix sort should not be considered a 'general purpose' sorting algorithm, for it requires fixed length integer keys; is it not useful otherwise. But I get your point. :) I guess my mistake was focusing on sorting aything that could be compared, instead of sorting integers, specifically. They are different problems, and have a different set of possible solutions. The question does mention "a random array of integers", but I admit I took it as an example, rather than a restriction. $\endgroup$ – rla4 Dec 4 '13 at 19:18
  • 2
    $\begingroup$ @DavidRicherby, looking back at this after a year and a half, I agree with you. Thank you. $\endgroup$ – D.W. Sep 20 '15 at 17:12
3
$\begingroup$

The fastest integer sorting algorithm in terms of worst-case I have come across is the one by Andersson et al. It has a worst-case of $O(n\log\log n)$, which is of course faster than $O(n\log n)$.

$\endgroup$
  • 2
    $\begingroup$ That's very interesting but you need to give more information. Since you mention $n\log n$, I assume you're aware that comparison-based sorting of general integers provably requires time $\Omega(n\log n)$. Anything asymptotically faster than that has to make assumptions about the data: for example, radix sort runs in linear time assuming that every element of the array is at most some constant. Under what conditions does this algorithm sort in $O(n\log\log n)$ and how does it perform in practice against other algorithms such as quicksort and radix sort? $\endgroup$ – David Richerby Sep 19 '15 at 21:01
1
$\begingroup$

I read through the other two answers at the time of writing this and I didn't think either one answered your question appropriately. Other answers considered extraneous ideas about random distributions and space complexity which are probably out of the scope for high school studies. So here is my take.

Given an array $A$ with $n$ integer elements, you need exactly $(n-1)$ comparisons between elements in order to check if $A$ is sorted (just start at the beginning of the array and check the next element against the last element). In fact, $(n-1)$ comparisons is the best case running time for any sorting algorithm. In other words, the running time lower boundary for any sorting algorithm is $\Omega(n)$. If you recall radix sort or bucket sort, you will notice that their running times are $O(n)$. Since all sorting algorithms are bound below by $\Omega(n)$, I would argue that both radix sort and bucket sort are the fastest algorithms for sorting an array of integers.

Additionally, if you are not familiar with what $\Omega(n)$ or $O(n)$: Both notations mean that the algorithm takes approximately $n$ operations to complete (could be $2n$ or $3n-5$, but not $1$ or $n^2$ operations).

$\endgroup$
  • $\begingroup$ Yes, but the $O(n)$ running time is also somehow almost cheating, since the constant in front of the $n$ effectively scales like $\lg n$ (since you are assuming a 32-bit machine model, and that implies that $n \le 2^{32}$). So, even though $O(n)$ (for radix sort) looks a lot better than $O(n \lg n)$ (for quicksort or mergesort), in practice the comparison is not quite so clear: the constants hidden in the big-O notation become very important, and the constant for radix-sort is higher than the constant for quicksort or mergesort. $\endgroup$ – D.W. Dec 3 '13 at 8:07
  • $\begingroup$ "the constant in front of the n effectively scales like $lg(n)$" I don't actually understand what you mean by this phrase (I understand that the Big-Oh notation hides constants which might be important for small $n$). $\endgroup$ – bourbaki4481472 Dec 3 '13 at 12:49
  • $\begingroup$ I think it's probably incorrect to say that the lower bound on any sorting algorithm is $\Omega(n)$. There may be sufficiently natural problems that admit assumptions which allow you to sort even faster than that. There are certainly sorting problems we might discuss academically which have faster algorithms. Of course, at that point, we may be debating what "sorting" actually is, and what the problem size really is, but the point remains. $\endgroup$ – Patrick87 Dec 3 '13 at 16:31
  • 2
    $\begingroup$ @D.W.'s point is that the true cost of radix sort is $O(wn)$, where $w$ is the word length. If you fix a constant $w$ and only sort numbers that can be written in $w$ bits (i.e., $\{0, \dots, 2^w-1\}$), you can sort in linear time. However, if you don't fix an upper bound on your numbers, it takes about $\log n$ bits to write your $n$ numbers, so $w=\log n$ and radix sort is running in time $n\log n$. $\endgroup$ – David Richerby Sep 20 '15 at 10:44
1
$\begingroup$

For integer sorting, the best known result seems to be: $$O(n \sqrt{log{ log{n}}})$$ in expectation using a randomized algorithm (or $O(n \sqrt{log{ log{U}}})$ if given an upper bound $U$), via Han, Thorup.

$\endgroup$
0
$\begingroup$

If you only allow making decisions by means of comparison of the keys, it is well-known that at least $\log(n!)$ comparisons are required in the worst case, to identify the comparison at hand among all the possible ones. This is an unbreakable bound.

If you allow other operations than comparisons, the trivial bound $\Omega(n)$ holds (and can be reached in special cases), as you have to read all the keys. This is unbeatable.

$\endgroup$
0
$\begingroup$

As you don't mention any restrictions on hardware and given you're looking for "the fastest", I would say you should pick one of the parallel sorting algorithm based on available hardware and the kind of input you have.

In theory e.g. quick_sort is O(n log n). With p processors, ideally this should come down to O(n/p log n) if we run it in parallel.

To quote Wikipedia: Time complexity of...

Optimal parallel sorting is O(log n)

In practice, for massive input sizes it would be impossible to achieve O(log n) due to scalability issues.

Here is the pseudo code for Parallel merge sort. Implementation of merge() can be same as in normal merge sort:

// Sort elements lo through hi (exclusive) of array A.
algorithm mergesort(A, lo, hi) is
    if lo+1 < hi then  // Two or more elements.
        mid = ⌊(lo + hi) / 2⌋
        fork mergesort(A, lo, mid)
        mergesort(A, mid, hi)
        join
        merge(A, lo, mid, hi)

Also see:

$\endgroup$
  • $\begingroup$ Quicksort is not really well suited for parallel processing in the standard form, which means that either any bitonic sorter should be better on average or the Quicksort is modified (more than intro sort, where merge phase is dominant) or the several split phases are done in host environment, which is counterproductive for parallelisation. In theory Quicksort is in fact $\mathcal O(n^2)$. $\endgroup$ – Evil Dec 8 '17 at 12:24
  • $\begingroup$ @Evil Yes. Quicksort isn't well suited for parallel processing. It's an example. The ones that should be used are listed in links given. $\endgroup$ – Kashyap Dec 8 '17 at 16:30

protected by Community Feb 3 '18 at 1:51

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.