[MTGandP]

This was a fascinating article. I do have a small correction: bucket sort is more similar to quicksort than merge sort.

merge sort bucket sort

1. divide (in half) 1. divide (in bins)

2. sort halves 2. sort bins

3. merge 3. done!

(Edit: Sorry, the formatting isn't great. I don't know how to do fixed-width text.)

The big difference here is that for merge sort, dividing the lists is trivial because all you have to do is split it into the first have and the second half. But for bucket sort, you have to actually look at each element to decide which bin it should go in. This is more like quicksort's partition step.