Lower Bound Argument
A sorted list has no inversions.
A reverse-order list has the maximum number of inversions, ?(n2) inversions.
A sorting algorithm must exchange ?(n2) adjacent pairs to sort a list.
A sort algorithm that operates by exchanging adjacent pairs of keys must have a time bound of at least ?(n2).