[Tutor] Merge Sort Algorithm

[Steven D'Aprano]

On Tue, Mar 28, 2017 at 03:56:16PM +0100, Elo Okonkwo wrote:
> Can someone pls explain this Merge Sort Algorithm, especially the Recursive
> bit of it.

Take a pack of cards and shuffle them. Now you want to sort the cards.

Put the cards down in a pile in front of you and think about sorting it. 
There are 52 cards in a Western deck of cards, so that's a lot of cards 
to sort. Let's make the job easier:

(1) Split the deck into two piles, half in each pile. Now you only 
have to sort 26 cards at a time, which is much easier.

(2) After you sort the first pile of 26, and then sort the second pile 
of 26, then you merge the two piles, keeping the same order: Turn the 
piles upside down, turn over the top card of each pile so you can see 
it, and start moving cards from the two piles to a third. Pick whichever 
card is smaller, move it to pile number 3, then turn over the next card 
so you can see what it is. Repeat until all the cards from the two piles 
are merged into a single pile, which is sorted.

Now comes the recursive step.

(3) In step 1, I said that sorting 26 cards is easier than sorting 52 
cards. This is true, but sorting 26 cards is still not that much fun. 
Let's make it easier: split the pile of 26 cards into two halves, and 
sort each half. Then merge the two halves together, and your pile of 26 
cards is sorted.

Recursive step:

(4) In step 3 I said that sorting 13 cards is easier than sorting 26 
cards. This is true, but sorting 13 cards is still not that much fun. 
Let's make it easier: split the pile of 13 cards into two (nearly) equal 
halves, and sort each half. Then merge the two halves together, and your 
pile of 13 cards is sorted.

Recursive step:

(5) In step 4 I said that sorting 7 cards is easier than sorting 13 
cards. This is true, but sorting 7 cards is still not that much fun. 
Let's make it easier: split the pile of 7 cards into two (nearly) equal 
halves, and sort each half. Then merge the two halves together, and your 
pile of 7 cards is sorted.

(6) In step 5 I said that sorting 4 cards is easier than sorting 7 
cards. This is true, but sorting 4 cards is still not that much fun. 
Let's make it easier: split the pile of 4 cards into two (nearly) equal 
halves, and sort each half. Then merge the two halves together, and your 
pile of 4 cards is sorted.

(7) In step 6 I said that sorting 2 cards is easier than sorting 4 
cards. This is true, but sorting 2 cards is still not that much fun. 
Let's make it easier: split the pile of 2 cards into two (nearly) equal 
halves, and sort each half. Then merge the two halves together, and your 
pile of 2 cards is sorted.

(8) In step 7 I said that sorting 1 card is easier than sorting 2 
cards. This is true, because 1 card is automatically sorted, and I 
don't have to think about it at all.


So merge sort takes a big job (sorting 52 cards) and repeatedly splits 
it into two smaller jobs, until the job is so simple even a computer can 
do it: sorting 1 card takes no brains at all. Then it merges 1 card and 
1 card together, keeping them in order, to get two. Then it goes back to 
the other pair of 1 card piles, and merges them. Then it merges the two 
piles of two cards to get a pile of four cards, and so on, until it ends 
up merging two sorted piles of 26 cards, and then the job is done.

You should actually try this as an exercise. Literally get a pile of 
cards and go through the steps until it makes sense.

For a *person*, this is not an efficient way to sort cards, but for 
computers it is very efficient, especially if you had millions of cards 
to sort.


-- 
Steve