Hacker News Reader

Comment by circlingthesun | Hacker News Reader

I had an interesting experience sorting exam papers when I was a TA. I found that quicksort used up too much desk/floor space. I settled on splitting the papers into piles of 10 or so, applying insertion sort on each pile and then pairwise merge sorting them until I had a sorted pile.

View on HN

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).

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.

I've has the same experience sorting trading cards. I did that frequently and experimented by applying different methods. I found the fastest for human execution was the same as you describe, insertion sort on small groups of 8-10 and then pairwise merge sort the piles until done.

I did the same, but I guessed the optimal number of piles is logarithmic in the number of papers, though I can't make further analysis. I naively split into log_e(200) = 5.29 = 5 piles. Also, if you place all the piles within vision, you can merge them all in one go, because the next paper should always be on top of some pile.

Reply on news.ycombinator.com