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