Find the least number of comparisons needed to sort (order) five elements and devise an algorithm that sorts these elements using this number of comparisons.

Solution: There are 5! = 120 possible outcomes. Therefore a binary tree for the sorting procedure will have at least 7 levels. Indeed, $2^h$ ≥ 120 implies $h $ ≥ 7. But 7 comparisons is not enough. The least number of comparisons needed to sort (order) five elements is 8.

Here is my actual question: I did find an algorithm that does it in 8 comparison but how can I prove that it can't be done in 7 comparisons?


5 Answers 5


The solution is wrong. Demuth [1; via 2, sec. 5.3.1] shows that five values can be sorted using only seven comparisons, i.e. that the "information theoretic" lower bound is tight in this instance.

The answer is a method tailored to $n=5$, not a general algorithm. It's also not very nice. This is the outline:

  1. Sort the first two pairs.

  2. Order the pairs w.r.t. their respective larger element.

    Call the result $[a,b,c,d,e]$; we know $a<b<d$ and $c<d$.

  3. Insert $e$ into $[a,b,d]$.

  4. Insert $c$ into the result of step 3.

The first step clearly takes two comparisons, the second only one. The last two steps take two comparisons each; we insert into a three-element list in both cases (for step 4., note that we know from $c<d$ that $c$ is smaller than the last element of the list at hand) and compare with the middle element first. That makes a total of seven comparisons.

Since I don't see how to write "nice" pseudocode of this, see here for a tested (and hopefully readable) implementation.

  1. Ph.D. thesis (Stanford University) by H.B. Demuth (1956)

    See also Electronic Data Sorting by H.B. Demuth (1985)

  2. Sorting and Searching by Donald E. Knuth; The Art of Computer Programming Vol. 3 (2nd ed, 1998)
  • 5
    $\begingroup$ The test gives five points for showing it is impossible. Wonder how many points you would get for your answer :-) (Probably zero since the test can't be wrong). $\endgroup$
    – gnasher729
    Nov 11, 2016 at 10:39
  • $\begingroup$ Knuth §5.3.1 finds that the minimum number of comparisons for all $n$ is $\sum_{k=1}^n \left\lceil \log_2 \frac34 k \right\rceil$ (A001768). The "information theoretic" lower bound is tight for $n\in [0,11]\cup\{20,21\}$. $\endgroup$
    – benrg
    Oct 10, 2023 at 8:24

The theoretical lower bound on comparison based sorting is $\log(n!)$. That is to say that to sort $n$ items using only $<$ or $>$ comparisons it takes at least the base 2 logarithm of $n!$, hence $\log(5!) \approx 6.91$ operations.

Since $5!= 120$ and $2^7= 128$, using a binary decision tree you can sort 5 items in 7 comparisons. The tree figures out exactly which of the 120 permutations you have, then does the swaps needed to sort it.

It's not pretty or short code, and you should probably use code generation methods to create the decision tree and swaps rather than coding it by hand, but it works; and provably works for any possible permutation of 5 items, thus proving you can sort 5 items in no more than 7 comparisons.

  • $\begingroup$ As far as I can remember, the theoretical lower bound gives an asymptotic lower bound (i.e., $\Omega(n \log n)$). Are you absolutely sure the constant factor is 1? $\endgroup$
    – dkaeae
    May 20, 2019 at 11:40
  • $\begingroup$ The theoretical lower bound for the worst case is ceil (log2 (n!)), because there are exactly n! permutations, and if there are k comparisons you need 2^k ≥ n!. It's not just a constant factor 1, it's exact. $\endgroup$
    – gnasher729
    Aug 24, 2019 at 15:16
  • $\begingroup$ @ron-peacetree - You seem to have changed the story partway through your answer: first you say ceil(log(n!)) is a lower bound on max number of comparisons needed (which is correct, and can be seen/proved simply by the argument that you need that many bits, i.e. decisions, to express which of the n! different cases is occurring). But then you assert something stronger: that it can always be done in ceil(log(n!)) comparisons (not decisions). Yes, 5 items can be sorted in no more than 7 decisions, but you haven't shown that it can be done in no more than 7 comparisons. $\endgroup$
    – Don Hatch
    Nov 23, 2021 at 13:42

Some problems are that the question is (1)incompletely stated, and (2)includes unwarranted presumptions:

how can I prove that it can't be done in 7 comparisons?

On the first point, it is unclear what the domain of the sorting problem is: is it random real numbers (with some specified or unspecified distribution), or integers (in some specified or unspecified range), or some other type of objects; are the values guaranteed to be distinct, or could there be duplicates (triplicates, etc.), and so on? If there are duplicates, etc., does it matter whether the partial ordering of items which compare equal is maintained (a.k.a. stable sorting)? None of these things are specified, and they all affect possible (and/or inapplicable) potential solutions to the sorting problem which is behind the stated question. It's also unclear whether the question is about best-case, average-case, or worst-case comparisons (under some specified conditions for some problem domain). And it's unclear whether anything other than comparisons (e.g. amount of data movement, partial-order stability as mentioned above, etc.) is a consideration.

On the second point, one of the responses notes Demuth's 7 comparison solution to non-stable sorting, so the question as stated is an impossible quest; one cannot in fact (correctly) prove the impossibility of something which is in fact possible.

So the short answer to the question as stated is "you can't" (in part because there is a 7 comparison solution to sorting 5 elements with certain constraints (and lacking others), and partly because the question and background do not specify any relevant constraints, details of the problem domain, etc.).


i was thinking quicksort. you select as pivot the element that just happens to be the middle element. compare the pivot to the remaining 4 items resulting in two piles to be sorted. each of those piles can be sorted in 1 comparison. unless i have made a terrible mistake, the 5 items were fully sorted in just 6 comparisons and i think that is the absolute fewest number of comparisons needed to do the job. the original question was find the least number of comparisons to sort 5 elements.

  • 1
    $\begingroup$ How can a pile of 3 elements be sorted in 1 comparison? $\endgroup$
    – xskxzr
    Aug 24, 2019 at 3:26
  • $\begingroup$ what 3 element pile are you talking about? what i described above produces 2 piles of 2 elements after the first pass. $\endgroup$
    – scottyc
    Sep 7, 2019 at 18:57
  • $\begingroup$ I thought that you use a random element as pivot. How can you select the middle element as pivot in 4 comparisons? $\endgroup$
    – xskxzr
    Sep 8, 2019 at 3:33
  • $\begingroup$ that's not what i'm saying. from above "Since 5!=120 .... using a binary decision tree you can sort 5 items in 7 comparisons." the number of permutations of the elements is 120 but there must be a branch that has only 6 comparisons because a random sample running of quicksort took only 6 to do the job. one of the 120 permutations is for the sorted list. that branch could contain as few as 4 comparisons. $\endgroup$
    – scottyc
    Sep 17, 2019 at 23:18

If you can test algorithm, test it on all number combinations. If you have lot of number, test on lot of random combinations. Not precise, but faster than all combinations.

a < b < c = 2
a < b < c < d = 3
a < b < c < d < e = 4


Insert to middle use 3-6 for 4 numbers.
Merging use 4-5 for 4 numbers.
Minimal compare by wiki is 5 for 4 numbers :) For 5 is 7. You use 8, still so much.
If you know all before comparations, you can go down with comparations. My average for 4 numbers is 3.96 / 1024 all combinations.

  • 2
    $\begingroup$ This doesn't answer the question. The question asks how to prove that there is no way to sort using only 7 comparisons. To use your approach, we'd have to enumerate all algorithms that use at most 7 comparisons. I think there are too many such algorithms to enumerate in a reasonable amount of time. In any case, I don't see what this adds over the existing answer, which already gave a complete answer to the question. We'd prefer that you focus on answering questions where you can add something new. $\endgroup$
    – D.W.
    Feb 6, 2018 at 13:43
  • $\begingroup$ Add is graphic and tip for alg. for predict cmp value from before cmp. And his min is 7, other sources 8, true min. is 4!!! 4 is work only for asc/desc order. Ex1: 00000 01234 43210 10000 ... Ex2: Insert to middle: 43210, start 4, get 3, cp 4>3, get 2, cp 4>2, cp 3>3, get 1, cp(mid) 3>1, cp 2>1, get 0, cp(mid) 3>0, cp 2>0, cp 1>0... 8 cmp. 7 can be possible for conncrete order or alg. You can look on my page for 4 numbers mlich.zam.slu.cz/js-sort/x-sort-x2.htm , Average 3.96. min-max 3-6. Can change for 5 and test his alg. $\endgroup$ Feb 8, 2018 at 11:23

Your Answer

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

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