The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

A Sorting Lower Bound

Date: 10/01/98 at 07:28:15
From: John Smither
Subject: Lower Bound Proof


I have the following university problem:

Show that you cannot sort 3 elements with 2 comparisons. This is an 
example of lower bound.  

Can you help?


Date: 10/01/98 at 09:08:24
From: Doctor Rob
Subject: Re: Lower Bound Proof

There are six possible orders for the three numbers. Each comparison
splits this set of orders into two sets, one of which agrees with the
results, and one of which doesn't. Two comparisons will split the set 
of orders into four sets. At least one of these sets must contain at 
least two of the orders, by the Pigeonhole Principle. Those two cannot 
be distinguished by this procedure. You fill in the details and 

Here is another proof. If the two comparisons only involve two of the
three elements, the second one is redundant, and the size of the third
element relative to the first two will remain unknown. Thus the two
comparisons must involve all three elements. Let the common element be 
a, and the first comparison a vs. b, the second a vs. c. No matter the
results, the relative sizes of b and c will remain unknown, unless a 
is the middle element, which cannot be guaranteed ahead of time, and 
happens only part of the time at random. We cannot improve on this by 
comparing a vs. b, and then c vs. max(a,b), since if c is smaller than 
max(a,b), we will not be able to tell whether or not c is larger than 
min(a,b). Similarly, comparing c to min(a,b) won't work either. There 
is essentially nothing else to try.

- Doctor Rob, The Math Forum   
Associated Topics:
High School Analysis

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.