4

What is the fastest known sort algorithm for absolute worst case? I don't care about best case and am assuming a gigantic data set if that even matters.

Improve this question
9
  • 3
    Tell us more about your specific scenario so people can suggest pros and cons of common sort algorithms. Otherwise I don't think there is any definitive answer. Commented Apr 21, 2009 at 15:45
  • 2
    I suggest you make it clear whether you care only about Big O notation or whether the constants involved in the ON log N) implementations matter. Radix sorts and the like add some confusion since they are very data dependent (and your question is too short) Commented Apr 21, 2009 at 15:49
  • I am talking if the worst possible case for one algorithm is n^2 and the other is n-log-n, the latter would win for a large data set even if the scenerio for the n^2 is very very rare to come by. Commented Apr 21, 2009 at 15:50
  • @Greg: O(n log n) is the theoretical best possible complexity for any comparison-based sort. There are a number of algorithms that have O(n log n) worst-case complexity (see the table at en.wikipedia.org/wiki/Sorting_algorithm). Commented Apr 21, 2009 at 15:53
  • Please update the question title to reflect the specific question, I recommend: "What sort algorithm provides the best worst-case performance?" Commented Apr 21, 2009 at 15:56

16 Answers 16

Reset to default
17

make sure you have seen this:

visualizing sort algorithms - it helped me decide what sort alg to use.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Visualizing sort algorithm is a wonderful way to experiencing different algorithms but it's also good to note something like hatfulofhollow.com/posts/code/visualisingsorting/index.html
9

Depends on data. For example for integers (or anything that can be expressed as integer) the fastest is radix sort which for fixed length values has worst case complexity of O(n). Best general comparison sort algorithms have complexity of O(n log n).

Improve this answer

1 Comment

+1 I just realized that this is the fastest if N>10, Best and Worst Case: O(n)
7

If you are using binary comparisons, the best possible sort algorithm takes O(N log N) comparisons to complete. If you're looking for something with good worst case performance, I'd look at MergeSort and HeapSort since they are O(N log N) algorithms in all cases.

HeapSort is nice if all your data fits in memory, while MergeSort allows you to do on-disk sorts better (but takes more space overall).

There are other less-well-known algorithms mentioned on the Wikipedia sorting algorithm page that all have O(n log n) worst case performance. (based on comment from mmyers)

Improve this answer

Comments

6

For the man with limitless budget

Facetious but correct: Sorting networks trade space (in real hardware terms) for better than O(n log n) sorting!

Without resorting to such hardware (which is unlikely to be available) you have a lower bound for the best comparison sorts of O(n log n)

O(n log n) worst case performance (no particular order)

Beating the n log n

If your data is amenable to it you can beat the n log n restriction but instead care about the number of bits in the input data as well

Radix and Bucket are probably the best known examples of this. Without more information about your particular requirements it is not fruitful to consider these in more depth.

Improve this answer

Comments

3

Quicksort is usually the fastest, but if you want good worst-case time, try Heapsort or Mergesort. These both have O(n log n) worst time performance.

Improve this answer

1 Comment

thank you for providing a straightforward answer rather than making things even more complex.
2

If you have a gigantic data set (ie much larger than available memory) you likely have your data on disk/tape/something-with-expensive-random-access, so you need an external sort.

Merge sort works well in that case; unlike most other sorts it doesn't involve random reads/writes.

Improve this answer

Comments

1

It largely is related to the size of your dataset and whether or not the set is already ordered (or what order it is currently in).

Entire books are written on search/sort algorithms. You aren't going to find an "absolute fastest" assuming a worst case scenario because different sorts have different worst-case situations.

Improve this answer

Comments

1

If you have a sufficiently huge data set, you're probably looking at sorting individual bins of data, then using merge-sort to merge those bins. But at this point, we're talking data sets huge enough to be VASTLY larger than main memory.

I guess the most correct answer would be "it depends".

Improve this answer

Comments

1

It depends both on the type of data and the type of resources. For example there are parallel algorithms that beat Quicksort, but given how you asked the question it's unlikely you have access them. There are times when the "worst case" for one algorithm is "best case" for another (nearly sorted data is problematic with Quick and Merge, but fast with much simpler techniques).

Improve this answer

Comments

1

It depends on the size, according to the Big O notation O(n).

Here is a list of sorting algorithms BEST AND WORST CASE for you to compare. My preference is the 2 way MergeSort

Improve this answer

3 Comments

According to en.wikipedia.org/wiki/Sorting_algorithm, there are at least six comparison-sorting algorithms with O(n lg n) worst case (which is the theoretical minimum).
true, which the link shows..there is a tie, but implementation Mergesort is what I prefer
My favorite is the merge sort too. It's stable, has guaranteed worst case performance of O(n log n), is easy to understand and write, and is amenable to large data sets that don't fit into memory.
0

Assuming randomly sorted data, quicksort.

O(nlog n) mean case, O(n^2) in the worst case, but that requires highly non-random data.

You might want to describe your data set characteristics.

Improve this answer

6 Comments

But the OP asked for absolute worst case -- in which case quicksort is N^2.
The OQ was for fastest known sort algorithim in worst case. O(n^2) would not qualify.
@Steve, maybe you're not getting what people are saying here, they are saying the question is what is the fastest algorithm in worst case scenario, not what are sorting algorithms worst case..quicksort does not fall in this category
I do get it, and I get that this answer is not addressing that point, I'm just saying -1 seems a bit harsh because that answer is clear and qualifies that QS is indeed o(n^2) in worst case.
Why would you presume to know what the author wants? Shouldn't the author be the authority on that? He seems to have spelled it out fairly clearly to me.
|
0

See Quick Sort Vs Merge Sort for a comparison of Quicksort and Mergesort, which are two of the better algorithms in most cases.

Improve this answer

Comments

0

It all depends on the data you're trying to sort. Different algorithms have different speeds for different data. an O(n) algorithm may be slower than an O(n^2) algorithm, depending on what kind of data you're working with.

Improve this answer

Comments

0

I've always preferred merge sort, as it's stable (meaning that if two elements are equal from a sorting perspective, then their relative order is explicitly preserved), but quicksort is good as well.

Improve this answer

1 Comment

Quicksort is O(n^2) in the worst case; modern implementations are usually designed to make that worst case exceedingly unlikely. Heapsort has O(n ln n) worst-case behavior, and requires O(1) additional memory.
0

The lowest upper bound on Turing machines is achieved by merge sort, that is O(n log n). Though quick sort might be better on some datasets.

You can't go lower than O(n log n) unless you're using special hardware (e.g. hardware supported bead sort, other non-comparison sorts).

Improve this answer

2 Comments

Since the data for a turing machine is on tape, quick sort is going to be very slow compared to merge sort on almost all nontrivial datasets.
How do you sort in O(n log n) with a single tape?
0

On the importance of specifying your problem: radix sort might be the fastest, but it's only usable when your data has fixed-length keys that can be broken down into independent small pieces. That limits its usefulness in the general case, and explains why more people haven't heard of it.

http://en.wikipedia.org/wiki/Radix_sort

P.S. This is an O(k*n) algorithm, where k is the size of the key.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.