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