Sorting - Not just for computers

Ok so this isn't strictly business, but I thought it was pretty cool.  My undergraduate degree was in Computer Science.  Fascinating subject, all about problem solving and algorithms.  Sadly I wasn't cut out to be a programmer.  There's a difference between doing a project for a class once, and programming 40 hours a week.  So after my degree I ended up taking work that was completely unrelated to my B.Sc.

In one of these jobs I was a shipper and almost daily I had to sort through stacks of invoices and mail them out, putting multiple invoices to the same customer in the same envelope if possible.  At first it was a time consuming process, but then I thought that maybe, just maybe, the sorting algorithms from my computer science days might just come in handy.

Sorting Algorithms

Imagine a deck of cards that you're trying to put in numerical order by suit (say, clubs, spades, hearts, diamonds).  Most people would sort this by what is called Insertion Sort.

Insertion Sort: put the cards on the table, pick them up one at a time, putting them in order in your hand as you go.

Thing is that for each card you pick up you have to compare it to every card in your hand.  For a few cards, not a big deal, but as the number grows larger, each new card you insert takes longer and longer to place.  If you have n cards, the total number of comparisons per card is at maximum, the number in your hand (which, at the end of the pile is n).  So this way with 52 cards will take you somewhere in the ballpark of 52*52 or 2704 comparisons.  With 100 things to sort you get up to 10,000 comparisons.  With 1000 items, it's 1,000,000 comparisons.  ugh.

There's a faster way.  It's called Merge Sort.  I knew it was faster on computers but I was like.... will this work in real life?  well I tried it and it does work and it's faster.  What you do is  you spread all the cards to be sorted out on the table (piles of one).  Then you merge the piles.  You start with two piles, look at the top card and flip the lowest face down between the two piles.  then the next lowest.  Continue for all the piles.  With n items to be sorted, you end up with n/2 piles.  Flip them all back over, and merge again.  take two piles face up, then put the lowest face down in the middle until the piles are merged.  you'll end up with n/4 piles.  Continue until there's only one pile.

This guy does a pretty good job of demonstrating it.

This takes n comparisons for each round, and there will be log(n) rounds.  So for 100 items to sort it will take 100*log(100) or 1000 comparisons.  This is a lot faster than the 10,000 we were looking at before.  For 1000 items you'll have 100,000 comparisons.  That's 1/10 the time insertion sort would have taken you.

So in the end, figuring this out came in very much handy for my job as a shipper of posters.  Now if ever you have to sort many things for some reason you can sort them faster than you could before.  Maybe every administrative position should require a computer science degree.