Hacker News Reader

Comment by barkingcat | Hacker News Reader

I can't recall the last time I've ever had to sort christmas ornaments.

And if you did, I imagine you could perform the task just fine without advanced knowledge of sorting algorithms.

I find the idea that the OP’s computer science background was a “help” hilarious. I’m sure those he was helping sort Christmas decorations with are all wondering how they ever managed to do it in the past, alone, without the Christmas miracle of sorting algorithms...

It makes me wonder what the most practical sorting algorithm for sorting things by hand is- like, if someone tossed a 1000-page hand-written (but numbered) manuscript in the air, which algorithm would be fastest to sort them by hand? Card sorters used radix sort, but if you don't have a card sorting machine, maybe mergesort.

According to Algorithms To Live By (great book), libraries use a sort of merge sort.

Someone on HN mentioned the 'magic of ____ arrays' or something like that where search, insertion, merge, etc. were all constant time operations...

Ah! Clojure's persistent vectors: https://hypirion.com/musings/understanding-persistent-vector...

I would use stacks to sort. The book was about 1000 pages? I'll do about 10 stacks. Then figuring out which stack to put a given page in is fast. (Abstract this and you wind up with a binary tree, which is what made me think of the persistent vectors above.)

The correct sort for that situation is a most-significant-digit-first variant of a radix sort. Arrange the documents into 10 piles based on hundreds digit. Pile up all of them except the zeroes, then sort the zeroes recursively. Then pull the next segment out of the pile, and sort it recursively. And so on.

This is often the most efficient way to sort physical items when you have a constrained range and working space, without custom equipment.

And yes, it really helps to know about variants like the American Flag Sort to realize that you can mix and match algorithm properties. AFS is an in-place sort, which is horribly inefficient for physical objects, but the observation that you can do a radix sort in MSD order is a refreshing additional observation vs "radix sort is always LSD first" the way card sorters work.

Some of my friends are postal workers and have described their mail sorting to be roughly this. It's not a general algorithm though, there is knowledge of their route weaved in. So the most significant bit would be the street name, but they'd remember houses 42+ are earlier in the route and direct them to a different bucket. For this reason the person delivering the mail also sorts it.

Computer science isn't directly applicable because we generally deal with general purpose algorithms, but I wonder how often their work is applicable to us, how often could we see huge improvements by using a specialized for the purpose sorting algorithm?

Can’t tell if OP was being sarcastic or not

I have a set of ornaments of the twelve days of Christmas. Last year I sorted them into order so that I could easily make sure that they were in ascending order on the tree. I'm going to do the same thing in two days time when we put our tree up again. I'll admit that I did it by eye, putting 1 and 12 at opposite ends of a table and then slotting the others into what seemed like the right places.

I can't remember the last time I've sorted anything with an algorithm written by me. Last time I did that in AI class in College. :\

I just don't see a reason to spend excessive time optimizing, unless performance becomes an issue.

Ah, you and your fancy non-OCD brain.

Reply on news.ycombinator.com