MergeSort Algorithm
Goals
Students will understand elements of the mergesort algorithm, which equally divides the cards into smaller collections and then merges sorted sub-collections.
Video
Materials
One deck of Acorn cards.
Setup
Shuffle the deck and deal each student 8 cards.
Each student will shuffle their 8 cards, and deal them face-down in a row in front of them, as shown below. These will define their initial collection of cards.
Algorithm
If the collection has more than one card, divide the collection in half by shifting the cards in the left collection slightly up. If the number of cards in the collection is odd, then make the left sub-collection hold one more card than the right sub-collection.
Repeat this algorithm on each sub-collection until there is only one card in your sub-collection, so that sub-collection is internally sorted.
Once the sub-collection algorithm is complete, use the Merge Two Sub-collections section below to recombine your two sub-collections into one collection.
Flip all the cards face-up. They should be in sorted order!
Merge Two Sub-collections
With two sorted sub-collections, we can create one large sorted collection quickly.
Flip the left-most card of each sub-collection face-up. These cards will be the front cards of the sub-collections.
-
Compare the front cards of the sub-collections. Add the smallest front card to the right of the last card in the merged collection. If this is the first comparison, then this card becomes the first card in the merged collection.
-
When the front of a sub-collection is removed, flip the next card in the sub-collection face-up to become the new front. As long as there are two front cards to compare, repeat the previous step. Otherwise, move all the cards in the remaining sub-collection in order to the right-hand side of the merged collection.
-
Flip the merged collection face down.
Example
We start with our initial collection of 8 cards face down.
We have 8 cards, more than one, in our initial collection, so we will divide our initial collection in half by shifting the Left half of the collection up. Since 8 is an even number, the left sub-collection will have 4 cards.
We have 4 cards, more than one, in our first sub-collection, so we will divide our sub-collection in half by shifting the Left half of the collection up. Since 4 is an even number, the left sub-collection will have 2 cards.
We have 2 cards, more than one, in our first sub-collection, so we will divide our sub-collection in half by shifting the Left half of the collection up. Since 2 is an even number, the left sub-collection will have 1 card.
There is only one card in our first sub-collection, so we can flip it up and see that it is internally sorted.
We flip down our internally sorted first sub-collection. There is only one card in our second sub-collection, so we can shift it up, flip it up, and see that it is internally sorted.
We flip down our internally sorted second sub-collection. Now we have two internally sorted sub-collections so we need to start the Merge Two Sub-collections process. We flip the left-most card of each sub-collection face up to become the front cards.
We shift down the smallest front card 27, since this is the first comparison this is the start of our merged collection. Since there is only one front card 63 left in the sub-collections, all cards in the remaining sub-collection (only 63 remains in its sub-collection) are shifted down, in order, to the right-hand side of the merged collection.
We flip down our merged collection and move on to the next sub-collection. We have 2 cards, more than one, in this sub-collection, so we will divide our sub-collection in half by shifting the Left half of the collection up. Since 2 is an even number, the left sub-collection will have 1 card.
There is only one card in our first sub-collection, so we can flip it up and see that it is internally sorted.
We flip down our internally sorted first sub-collection. There is only one card in our second sub-collection, so we can shift it up, flip it up, and see that it is internally sorted.
We flip down our internally sorted second sub-collection. Now we have two internally sorted sub-collections so we need to start the Merge Two Sub-collections process. We flip the left-most card of each sub-collection face up to become the front cards. The smallest front card 18, becomes the start of our merged collection since this is the first comparison. Since there is only one front card 50 left in the sub-collections, all cards in the remaining sub-collection (only 50 remains in its sub-collection) are moved, in order, to the right-hand side of the merged collection.
We flip down our merged collection. Now we have two internally sorted sub-collections so we need to start the Merge Two Sub-collections process. We flip the left-most card of each sub-collection face up to become the front cards.
We shift down the smallest front card 18, since this is the first comparison this is the start of our merged collection. Since there is another card in the sub-collection of 18 we flip it up to become our next front card, 50.
We shift down the smallest front card 27, and add it to the right-hand side of the merged collection. Since there is another card in the sub-collection of 27 we flip it up to become our next front card, 63.
We shift down the smallest front card 50, and add it to the right-hand side of the merged collection.
Since there is only one front card 63 left in the sub-collections, all cards in the remaining sub-collection (only 63 remains in its sub-collection) are shifted down, in order, to the right-hand side of the merged collection.
We flip down our merged collection and move on to the next sub-collection. We have 4 cards, more than one, in this sub-collection, so we will divide our sub-collection in half by shifting the Left half of the collection up. Since 4 is an even number, the left sub-collection will have 2 cards.
We have 2 cards, more than one, in our first sub-collection, so we will divide our sub-collection in half by shifting the Left half of the collection up. Since 2 is an even number, the left sub-collection will have 1 card.
There is only one card in our first sub-collection, so we can flip it up and see that it is internally sorted.
We flip down our internally sorted first sub-collection. There is only one card in our second sub-collection, so we can shift it up, flip it up, and see that it is internally sorted.
We flip down our internally sorted second sub-collection. Now we have two internally sorted sub-collections so we need to start the Merge Two Sub-collections process. We flip the left-most card of each sub-collection face up to become the front cards. The smallest front card 19 is shifted down and becomes the start of our merged collection since this is the first comparison. Since there is only one front card 52 left in the sub-collections, all cards in the remaining sub-collection (only 52 remains in its sub-collection) are shifted down, in order, to the right-hand side of the merged collection.
We flip our merged collection down and move on to the next sub-collection.
We have 2 cards, more than one, in this sub-collection, so we will divide our sub-collection in half by shifting the Left half of the collection up. Since 2 is an even number, the left sub-collection will have 1 card.
There is only one card in our first sub-collection, so we can flip it up and see that it is internally sorted.
We flip down our internally sorted first sub-collection. There is only one card in our second sub-collection, so we can shift it up, flip it up, and see that it is internally sorted.
We flip down our internally sorted second sub-collection. Now we have two internally sorted sub-collections so we need to start the Merge Two Sub-collections process. We flip the left-most card of each sub-collection face up to become the front cards. The smallest front card 01 is the start of our merged collection since this is the first comparison. Since there is only one front card 44 left in the sub-collections, all cards in the remaining sub-collection (only 44 remains in its sub-collection) are moved, in order, to the right-hand side of the merged collection.
We flip down our merged collection. Now we have two internally sorted sub-collections so we need to start the Merge Two Sub-collections process. We flip the left-most card of each sub-collection face up to become the front cards.
We shift down the smallest front card 01, since this is the first comparison this is the start of our merged collection. Since there is another card in the sub-collection of 01 we flip it up to become our next front card, 44.
We shift down the smallest front card 19, and add it to the right-hand side of the merged collection. Since there is another card in the sub-collection of 19 we flip it up to become our next front card, 52.
We shift down the smallest front card 44, and add it to the right-hand side of the merged collection.
Since there is only one front card 52 left in the sub-collections, all cards in the remaining sub-collection (only 52 remains in its sub-collection) are shifted down, in order, to the right-hand side of the merged collection.
We flip down our merged collection. Now we have two internally sorted sub-collections so we need to start the Merge Two Sub-collections process. We flip the left-most card of each sub-collection face up to become the front cards.
We shift down the smallest front card 01, since this is the first comparison this is the start of our merged collection. Since there is another card in the sub-collection of 01 we flip it up to become our next front card, 19.
We shift down the smallest front card 18, and add it to the right-hand side of the merged collection. Since there is another card in the sub-collection of 18 we flip it up to become our next front card, 27.
We shift down the smallest front card 19, and add it to the right-hand side of the merged collection. Since there is another card in the sub-collection of 19 we flip it up to become our next front card, 44.
We shift down the smallest front card 27, and add it to the right-hand side of the merged collection. Since there is another card in the sub-collection of 27 we flip it up to become our next front card, 50.
We shift down the smallest front card 44, and add it to the right-hand side of the merged collection. Since there is another card in the sub-collection of 44 we flip it up to become our next front card, 52.
We shift down the smallest front card 50, and add it to the right-hand side of the merged collection. Since there is another card in the sub-collection of 50 we flip it up to become our next front card, 63.
We shift down the smallest front card 52, and add it to the right-hand side of the merged collection.
Since there is only one front card 63 left in the sub-collections, all cards in the remaining sub-collection (only 63 remains in its sub-collection) are shifted down, in order, to the right-hand side of the merged collection.
