[Tutor] Merge Sort Algorithm

[Elo Okonkwo]

Thanks so much everyone.

I've figured it out. It was the recursive bit that got me confused, its a
bit difficult debugging recursive functions.



On Wed, Mar 29, 2017 at 1:36 AM, Steven D'Aprano <steve at pearwood.info>
wrote:

> 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
> _______________________________________________
> Tutor maillist  -  Tutor at python.org
> To unsubscribe or change subscription options:
> https://mail.python.org/mailman/listinfo/tutor
>