Jeff Cooper

Applying Mergesort in a Latin Classroom

Note: This post was imported from my old blog, created and written in my high school years

16 Sep 2009

Today I was faced with a rather challenging quiz in AP Latin Class: Put the following events from book one of the Aeneid in chronological order.  There were 14 of them.  Now sure, I'd read book one, but I read it for overall themes, not individual points.  The quiz (thankfully) wasn't graded, but I didn't know that until after faced with this daunting question.  And for added fun, I was doing it in pen.  No mistakes.

I was staring at the various points on the page with no idea how to approach it.  There were fourteen points.  Five or so I could order mentally.  Fourteen I could not.  I couldn't recall line numbers for each point, as I read it in English, so no luck ordering by numbers.  So I started looking through the list, searching for the earliest one.  As my conscious was hard at work doing this menial task, my subconscious was laughing.  "This is like an insertion sort!  Looping through each one for comparison?  Shame on you, that's O(n^2)!"

Then it hit me: I was doing an insertion sort.  There was a better way.

Thankfully I had a large right-hand margin, as I used nearly all of it during my next step.  I drew a line between the first seven and last seven points.  Then I divided each again.  And again, until I had groups of two and three.  Perfect.  Now, instead of figuring out which event globally came first, I simply had to figure out which event in each group of two was first and which was last.  O(1), n times.  Then I had merge.  start with the earliest event in each adjacent group.  Which was earlier?  Put it first and move my finger to the next one in that list.  Repeat.  This was a rather tedious process, but brainless: all I had to do was see which of the two events my fingers were pointing to happened first.  Easy.

I repeated this process several times until I had a single group.  Near-perfect mergesort, by hand.  The only difference was the comparison.  Not greater-than or less-than, but before or after.  And if I hadn't placed Mercury's arrival at Carthage where Cupid's was (and misplaced a dramatic interlude by Venus), I would have gotten them all right.

I highly recommend that the general public learn mergesort.  It is my favorite real-life sorting algorithm; I use it to sort decks of cards, and now I use it on tests.  Yes, it's not an in-place algorithm, so you need some space to spread out, but you don't really need "markers" as you do in something like quicksort.  While quicksort uses less memory (or in the real life scenario, desk space) by being in-place, mergesort is comprehensible by even the worst mathematicians.  Which one's bigger?  That's all you need to know.

comments powered by Disqus