Discussion

This looks at the most significant bit, partitions the list into those with a zero there and those with a one. (Like quicksort.)

At this point, we can sort the two sublists separately.

Recurrence: T(n,0) = 0, T(n,b) = n + T(a,b-1) + T(n-a,n-1) (for some $1 \le a \le n$).

Can prove by induction that this gives T(n) = bn.