Data Structures & Algorithms Lecture Notes

20 April 2010 • Faster Sorting


Where did that come from? Start with

1: a, b = min(a, b), max(a, b)

// a ≤ b

2: b, c = min(b, c), max(b, c)

// b ≤ c ∧ a ≤ c

3: a, b = min(a, b), max(a, b)

// a ≤ b ≤ c

The values of c in statement 2 and a in statement 3 can be ignored.

1: a, b = min(a, b), max(a, b)
2: b = min(b, c)
3: b = max(a, b)

Replace in statement 3 the value of b computed in statement 2.

1: a, b = min(a, b), max(a, b)
3: b = max(a, min(b, c))

Replace in statement 3 the values of a and b computed in statement 1.

3: b = max(min(a, b), min(max(a, b), c))


This page last modified on 24 January 2006.