[kadoban]

Bucket sort can be pretty effective physically. An example would be separating the papers by first initial if you're sorting by name (pick whatever matches your sorting key), then sorting each bucket individually (pick whatever seems appropriate, another layer of buckets or just insertion sort for instance). When you've sorted each bucket, you just put the buckets in order, no real merge work needed.

You can adapt what you're doing by how the buckets look (huge bucket? do another layer of bucketing in there. Small bucket? Just sort it) and it's easy to see progress and you can "discard" buckets as you go (put them in one output pile as they're done).

[klipt]

In a way, quick sort, radix sort and merge sort are all just recursive versions of bucket sort :-)

* Merge sort: sort within buckets, then between buckets

* Quick sort: sort between buckets, then within buckets.

* Radix sort: can be either depending on whether you sort by most or least significant radix first.

Humans can handle dividing into more than 2 at each stage though, so sorting 100 things with 10 piles of 10 tends to be easier than 7 binary divisions.