Introduction

To find the median of three values, you need at most three comparisons. That is the standard worst-case answer. But the full story is slightly more interesting: some input orders can finish in two comparisons, while the worst case still requires three.

Why Three Is the Worst-Case Minimum

There are six possible orderings of three distinct elements. A comparison-based decision process must distinguish enough cases to identify the middle value.

After one comparison, you only know the order of one pair. After two comparisons, some branches still leave two possible medians. So in the general case, a third comparison is necessary.

That means:

• best case: 2 comparisons
• worst case: 3 comparisons

An optimal comparison tree achieves exactly that.

A Simple Median-of-Three Implementation

1def median_of_three(a, b, c):
2    comparisons = 0
3
4    comparisons += 1
5    if a < b:
6        comparisons += 1
7        if b < c:
8            return b, comparisons
9
10        comparisons += 1
11        if a < c:
12            return c, comparisons
13        return a, comparisons
14    else:
15        comparisons += 1
16        if a < c:
17            return a, comparisons
18
19        comparisons += 1
20        if b < c:
21            return c, comparisons
22        return b, comparisons
23
24
25print(median_of_three(1, 2, 3))
26print(median_of_three(1, 3, 2))

For (1, 2, 3), it returns after two comparisons. For (1, 3, 2), it needs three.

Why Some Cases Need Only Two

Suppose you first compare a and b, then compare b and c.

If you learn:

• 'a < b'
• 'b < c'

then the order is already a < b < c, so b is clearly the median after only two comparisons.

But if you learn:

• 'a < b'
• 'c < b'

you still do not know whether the order is a < c < b or c < a < b. A third comparison between a and c is needed.

Average Number of Comparisons

If all six orderings are equally likely and you use an optimal decision tree, four cases finish in three comparisons and two cases finish in two comparisons.

So the average is:

(4 * 3 + 2 * 2) / 6 = 8 / 3

That is about 2.67 comparisons on average.

In Quicksort Context

When people talk about "median of three" in quicksort, they often mean choosing the pivot from the first, middle, and last elements. The pivot-selection step itself has the comparison cost described above, but the total sort cost also includes:

• the partition pass
• recursive calls
• swaps or moves

So saying "median of three uses three comparisons" is correct only for the pivot-selection subroutine in the worst case, not for the whole partitioning process.

Common Pitfalls

The biggest mistake is saying the median of three always uses exactly three comparisons. That is only the worst-case count.

Another mistake is confusing median selection with full sorting of three elements. Sorting all three also takes up to three comparisons, but the goal is different.

A third issue is forgetting that equal elements can change branch behavior in a concrete implementation, even though the classic analysis usually assumes distinct keys.

Summary

• Finding the median of three values takes at most three comparisons.
• Some input orders finish in only two comparisons.
• The worst-case minimum is still three comparisons.
• The average comparison count for an optimal method is 8/3.
• In quicksort, this cost applies only to pivot selection, not to the whole sort.