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

Hi!

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?

Thanks,
John
```

```
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
reasons.

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
http://mathforum.org/dr.math/
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search