Which sorting algorithm uses the fewest comparisons?

Question

Imagine a case where comparison of two elements is hugely expensive.

Which sorting algorithm would you use?

Which sorting algorithm uses the fewest comparisons in the average case?

What if you can expect a lot of the compared elements to be identical, say in 80% of the comparisons. Does it make a difference?

Rodmann

possible duplicate of Looking for a sort algorithm with as few as possible compare operations – Rennin

Are you accepting sorts that don't use comparisons? Not all sorts are comparison sorts (and thus don't fall under the O(nlog(n)) limit for comparison sorts) – Botnick

Possible duplicate: #1935694 – Embrocation

Answer 1

Quite Possibly Insertion Sort

---

Sorting is one of those subjects where, as they say, the devil is in the details. Typically, secondary considerations dominate the performance input parameters.

However, if comparisons are very expensive and if most keys are identical, it is possible that the input could be considered already sorted or already almost sorted.

In that case, what you want is a reasonable algorithm that has the fastest best case, and that would almost certainly be an insertion sort.

Gentleness

Why would you want to find an algorithm with the fastest best case (instead of an algorithm with the fastest average case)? – Embrocation

-1 This is a reasonable intuition, but it doesn't pan out in practice. Even for nearly-sorted lists, merge sort is way better than insertion sort for number of comparisons (see e.g. these experimental results) just because of how quickly n^2 vs. n log n catches up with you. – Avaria

Answer 2

Merge-insertion sort, a variant of insertion sort, was touted as the sorting algorithm with the fewest known comparisons for several decades, and is perhaps still the best freely-documented sorting algorithm for minimal comparisons:

Merge-insertion sort is the sorting algorithm with the minimum possible comparisons for n items whenever n ≤ 15 or 20 ≤ n ≤ 22, and it has the fewest comparisons known for n ≤ 46.

Glenn K. Manacher's algorithm “and later record-breaking sorting algorithms” (none of which, unfortunately, seem to be freely documented at this time) are reported to adapt the merge-insertion sort algorithm to offer even fewer comparisons.

Cissiee

Answer 3

The winner is Sleep Sort, which uses no comparisons.

Quyenr

After going through the link I find the algorithm is sleepy in literal sense. Because the algo has to wait for at least the time=largest_value, while rest of the sort algoes would be complete with sorting way before. But when the question is solely around minimizing the no. of comparison then this algo rocks!! :) – Scarecrow

Funny idea :) Although it assumes that converting the sort key to integer is easy. – Rodmann

I think the claim "no comparisons" is too strong and thus wrong - there must be at least n compares when iterating the elements (assuming the length of the array is unknown at compile time). Also: is sleep(time) a machine instruction? I believe the underlying OS will need some comparisons to implement it, though I am not certain of it (will be glad for clarification regarding it). (p.s. not the downvoter, still nice work around IMO) – Subprincipal

@amit: when we talk about comparisons in a sorting algorithm we are generally talking about comparisons of element values, and by this criterion Sleep Sort uses no comparisons. (sleep() is just an implementation detail - it could easily be implemented as a hardware timer interrupt.) Sleep Sort is not meant to be taken too seriously though - it's just a novelty - an amusing and interesting example of "outside the box" thinking. – Quyenr

Interesting idea. However sorting only requires a comparison function between two elements: there is no requirement that you might be able to convert individual elements to a duration. For instance we can ask people to sort items by preference without asking them to give an explicit rating for each item. We don't even need to assume such a rating exists. In the event the comparison function is implemented is such a way that it converts two elements to integers and returns according to their natural order, then sleepsort would require n such conversions, which is equivalent to N/2 comparisons. – Dendy

@marcv81: Sleep Sort isn't meant to be taken seriously - it's an interesting idea in that it's a valid sorting algorithm which doesn't use comparisons, but it has no practical use beyond that as far as I'm aware. – Quyenr

@PaulR: I understand it's not meant for real-life use! My point is that it does not technically qualify as a sorting algorithm, and that in the cases where you could actually implement it (and when comparisons are expensive as per OP) it would use the same amount of resources as N/2 comparisons. – Dendy

While funny, this presumes it is practicable to monotonously map key values to valid arguments of sleep. – Third

Yes, I understand this is a joke answer, however sleep sort is a distributive sort, so if you say that uses no comparisons, then radix sort would also be a perfectly valid answer. Although these are both true, I have a feeling this isn't what OP was looking for. – Esra

funny that a space-time trade-off works here. Just need a big array. – Impoverish

Answer 4

It's depends what data do you have. You need stable algorithm or not?

Where your data are uniformly you can use bucket sort ( Θ(n), O(n^2))

counting sort (I think it's what you are looking for), it's also stable algorithm, but need more memory (less is you have a lot of identical records).

Of course you can use Sleep sort, but if you have a lot of data it won't works.

If your elements are in 80% identical maybe there is a simple way to said there are identical (just the same)?

Trichite

Answer 5

Shellsort uses less comparisons.

And you have lot of identical elements, Counting sort should do the job

Maclay

Answer 6

maybe a non-comparative algorithm like radix sort might be the answer, because it s also fast in general case(takes time O(n)). also makes no comparisons between the elements but on the other hand it requires a lot of memory

Claudio

Answer 7

Distribution sort (using a hashing array) takes almost no comparisons.

m = max number  may appear in the input + 1
hash = array of size m
initialize hash by zeroes

for i = 0 to n - 1
    hash[input[i]] = hash[input[i]] + 1
j = 0
for i = 0 to m - 1
    while hash[i] > 0
        sorted[j] = i
        j = j + 1
        hash[i] = hash[i] - 1

Incisure