lOverall steps = cn x number of levels.
lO(log(n)) levels in optimistic case.
lO(n) levels in pessimistic case.
lOverall O(n2).
lThe average case can be shown to be O(n log(n)) based on a probabilistic
argument, assuming the data are initially randomly
distributed.