Recursive sorting, part 1

I thought I could get away with just a brief mention of QuickSort, but apparently some people really want to hear details.  So here you go.  Today I'm going to talk about something that is not QuickSort, but it is a closely related technique called a Merge Sort.  This is tangentially related to the discussion about Big O notation, but it's not really my main focus here.  I'll just tell you in advance that, like QuickSort, this takes a time of O(n log n).

Along the way, I'm going to have to explain the basics of recursion to the novices, who may have been a little uncertain about what to make of the story about my dream.

Understanding recursion

Imagine that I am playing the board game "Risk" and I have an objective to take over the world.  No wait, better idea.  Imagine that I am an Evil Genius, and my actual objective is to take over the world.

The world is a big place.  Too big to plan my attack in every minute detail by myself.  How am I going to go about this?

Presumably I need military commanders, so I'll assume that I have a number of Evil Generals at my Evil Headquarters, who are expert military strategists.  Luckily, the world is already divided up into several logical categories, known as continents.  So I formulate a plan.  First I'll conquer Europe.  Then I'll conquer Asia.  Then Africa.  Then Australia.  Then North America.  Then South America.  Conquering each region will help me gain additional bases, which will aid me in the remainder of my nefarious plans.

So I pick my six finest generals, and I say "Okay, listen up minions!  YOU.  Conquer Europe.  I don't care how you do it, just get the job done and report back to me.  YOU.  Conquer Asia."  And so on.  I assign one continent to each general.  Then I sit back and relax, confident that my brilliant generals will each do their job thoroughly and well.  My part in the plan is finished.

But continents are still big places, so my Generals now have quite a job in front of them.  Consider the poor General whose job it is to conquer Europe.  Where does he start?  Well, like me, the logical thing to do is divide up the work, and the way to do that is country by country.  "First I'll conquer France," he says.  (Ha ha, get it?  That's apparently screamingly funny if you're a neoconservative.  I aim to please a wide audience.)  "Then I'll conquer England.  Then Germany."  Etc.

So my Evil General calls in all of his Evil Colonels, and he says "Okay, you get France, you get England, you get Germany," etc.

The Colonel in charge of conquering England then calls all his Evil Majors and explains "You conquer London, you get Southampton, you get Lancashire," etc.

You can expect this process to trickle down through several more layers of authority, but here's the thing: you can't go on subdividing the territories forever.  You can't run an organization with only a bunch of managers, because sooner or later somebody has to do the actual work.  You can't have some little underling running around saying "Okay, you conquer this microbe, and you conquer that microbe."

What you need is a terminating condition.  On some level, you simply have to have a whole lot of Evil Privates, and the Evil Sergeants will point at the enemy and say "Go now and kill that guy over there."  Privates don't get to delegate.

So my Privates kill people, which is something that is in some way completely different from what everyone else is doing, which is just splitting up the territories and telling somebody else to do the work.

Eventually, all my Privates report to all my Sergeants, announcing "Territory secured, sir!"  Then all the Sergeants report to their respective Evil Lieutenants, and so it goes.  Up the chain, eventually reaching my Colonels, who say "Country secured!" and my Generals then come to me and say "Continent secured!" and then I chortle with glee in my Evil Lair.  "I've done it!" I say.  "I own all the continents, and the world is now mine.  MINE!  Mooha, mooha, mwahahahahaha haaaaaaaaaaa!!!"

Or words to that effect.  I'll work on my speech when the time comes.

Today, Merge Sort.  Tomorrow, the world

We've just covered a fundamental principle of recursion, known as "divide and conquer."  In this case, we talked about literally dividing and conquering territories of the world.  Now we're going to bring it back to the domain of sorting cards.

I give you an entire deck of cards to sort, and I say "Put these cards in order.  You have three minutes."  I know, those instructions are a little unclear because the suits can come in any order. Typically in a new, unshuffled deck, all the spades come first, then the hearts, then diamonds, then clubs; and then within the suits, the cards are ordered from Ace to King.  We'll assume that you and I both know and agree on the order of a "correctly" shuffled deck.

So you have three minutes to sort the cards.  Now, you know your card-sorting abilities really well, and you think to yourself, "Hmmm, I know how fast I can work.  I can finish about half a deck in two minutes.  If I do that I'll finish almost all the work, but not quite.  I'm gonna need some help."

So you call in a friend, who also knows everything there is to know about correctly sorted decks, and works just as fast as you do.  You say to your friend "Hey, glad you're here.  Here's what I want you to do.  I'm going to split these cards in half, and give half to you.  You sort your half, I'll sort my half.  Then when I'm done, we'll deal out our two sorted half-decks into one pile, or 'merge' them, and we'll have a whole sorted deck."

So you divide up the deck into two.  You have 26 cards, which you sort using your favorite technique (you can use selection sort if you want).  Your friend sorts his pack of 26 cards, and then you get together.

You have the ace of spades.  You lay it face up on the table.  Your friend has the two of spades.  He lays his down.  Your friend also has the three, so he lays another one down.  You have the four, so you lay it down.  You continue until the whole pack is done; flip the pack and you can deal them out in perfect order, ace first.

You finished your deck in two minutes, and your friend finished his deck in two minutes.  Both of you worked in parallel, so the two of you were done in just two minutes, not four.  Merging your decks goes pretty quickly, only taking up another minute.  Three minutes have elapsed, and you're done.

Double your fun

I tell you: "Great job sorting that pack, now I've got more for you to do.  I have two different packs of cards this time, all mixed together.  I want you to sort them out into two piles, one with blue backs and one with green backs.  I know this will take more time... I'll give you five minutes."

How long does it take to sort a whole deck?  From the last job, we know it takes three minutes.  Clearly five minutes won't be enough for two decks, so we're going to need more friends.

So we get two more people in on the action.  You tell your friend: "I'm going to split up these 104 cards into two piles of about 52 cards each.  You get your half sorted, and I'll get my half sorted.  Sort them the same way you did before, but this time always put blue cards before green cards."

But selection sort is way too slow, so you then take your 52 cards and turn to another friend.  You say "Now I have 52 cards.  You take 26 and I'll take 26, and we'll each sort them in two minutes."

Two minutes later, you're both done.  You take another minute to merge the decks.  Now you have 52 sorted cards.  It's been 3 minutes.

You turn to your friend and discover that, with the help of the fourth guy, he also has a sorted pack of 52.  You merge the cards -- there are more than before, but you finish dealing them together in another 2 minutes.  Five minutes are now up, and you have a single pile of perfectly sorted cards.  Then all you have to do is separate them in the middle, to get two decks.

Generalizing the solution to "n"

By now I'm sure you've got the idea.  I can sort four decks, or eight decks, or any number of cards I want.  All I need is more friends.  Your friends aren't "free" -- they take up a lot of space, demand lunch breaks, and if you're asking for a lot of work they might want to get paid.  If you don't like that, then you're free to go back to selection sorting the whole deck.  But with one person performing an O(n²) algorithm, the job will take hours if you have a lot of cards.  Much better to keep dividing and subdividing your packs until you have a manageable little pile, and then it gets easier to merge a few piles at a time.

The analogy to taking over the world should be clear.  "Divide and conquer" is in fact a well known program-writing technique.  Splitting the deck and handing the job to friends is directly analogous to filtering the world by smaller pieces of land, and then handing them to lower ranking underlings.

Another point this illustrates is the frequently recurring theme of trading space for time.  As I said before, the more friends you have sorting cards, the more costly the job is.  Inside the guts of your computer, what this means is that using a recursive algorithm eats up more of your computer's memory.  This can cause everything else in your operating system to run slower, if you start using up too much memory.

On the other hand, computers these days have a lot of memory, and unless you're trying to run World of Warcraft while you're computing, most of your memory is often sitting idle.  Why not throw more storage at the problem, if the time saved is so great?

Better yet, thanks to advances in parallel computing, it's now possible to actually physically divide up the work among multiple machines.  You order one computer to sort half the cards, and another computer to sort the other half.  Then you just take up a little network traffic to have them report to a master server, which consolidates the information.

One example of a popular program that takes this approach is the SETI@home project.  We may never discover intelligent life elsewhere in the universe.  But if we want to try, we've got massive task collecting readings from different areas of space.  SETI takes advantage of the idle time on computers whose owners have voluntarily installed their program.  Your desktop runs the program when you enter screen saver mode, analyzing different areas of space, and the SETI server gathers whatever interesting information that you discover.

Now that everyone's up to speed on the basics of divide-and-conquer, I'll go over QuickSort next time.