everyone get in alphabetical order!

we are all familiar with this task; taking an unsorted list and returning a copy sorted by some comparator is something we do in life all the time, as well as one of the most discussed topics in computer science with respect to algorithm cost and complexity. as with many inner geek moments, the question, "is there an optimal solution to this problem?" comes to mind.

when dealt a hand of cards, most people will perform some version of INSERTION SORT. in comparison to other methods of sorting, it's pretty bad (worst case O(n^2) even). luckily a person's actions are weighted very differently from a computers. comparing two (or lots) of elements has almost no cost relative to the amount of time it takes to actually rearrange the cards in their hand. (this is actually one of the reasons that i don't rearrange my cards when playing spades!) this makes insertion sort more along the lines of hO(n) - human O, the rate of growth for a human performing the algorithm.

to further show the difference between O and hO algorithms, see how long it takes you to perform MERGE SORT on a bunch of cards and see how much longer it takes.


another very interesting modification to this scenario is the end of recess in gradeschool. all of the kids get in line, but the teacher tells them to get into alphabetical order. instead of the teacher making comparisons and telling students to move around in line, the sorting happens sort of like this: each student looks at the person in front or behind and they make the decision, "should we switch places." keep doing this until everyone is happy.

as an exercise for my readers (i have readers?!) how much faster is this approach? would you model kids' behaviour differently?