Merge Sort and Lines of Kindergarteners

Merge sort is a recursive, sorting algorithm based on two intuitive principles:

1) It is easy to sort very short lists. In fact, it is trivial to sort lists containing only one item.

2) It is easier to merge together two sorted lists than it is to sort a long list.

Using those ideas, the merge sort algorithm can be described simply as: "Break the data to sort in half, sort each half separately using merge sort, and merge the halves back together into a single sorted list."

Ann's kindergarten teacher, Mrs. Magee, was fiercely competitive. She insisted that the class excel in everything. Her class always had the highest test scores. Her class always won at dodgeball. And, most important of all, her class could form a sorted line faster than any other class in the kingdom.

It did not matter how the class was being sorted. They could line up by height, by first name, by last name, by length of their left pinky toe, or even by their skill at dodgeball. Mrs. Magee would call out an attribute, and the class would spring into action.

Like all winning teams, their excellence depended on more than natural talent. In fact, most kindergarteners in the class were absolutely dreadful at sorting when they started school. Once, two students, Jack and Jake, had spent fifteen minutes trying to compare the order of their names. It was embarrassing.

The class's ability came from practice. Mrs. Magee drilled the class for hours at the start of the school year. Every time the students went to the bathroom or to lunch, she would first make them line up in some sorted order.

Of course, there was also a strategy -- Merge Sort. It was her secret weapon, her key to winning.

At the command "LINE UP!" the class would split into two equally sized groups.

Class before sorting

First split

Those groups would then each split into two smaller groups.

The splitting continued until each group had just a single person.

Then, starting from each pair of singletons, the groups would reform. Each child would look at their partner and quickly line up in order. With only two people it was easy. A single quick comparison provided the order.

After the groups of two were in order, the kids would merge into larger groups. Again, merging was simple -- you only needed to compare the two kids at the front of the two lines. The person with the smallest value had to be one of the first two kids, because the lines were sorted. The first two kids would compare, and one would step forward to start the new sorted line.

Merge Step 1

Now the second smallest still had to be one of the front two kids.

Merge Step 2

And so forth.

Merge Step 3

Merge Step 4

Merge Step 5

The lines would quickly merge together, forming larger groups. This would continue until the entire class was in order.

That is how Mrs. Magee's class won the sixth annual kingdom sorting championship. Her class was in order a full five minutes before the runners up. In fact, Mr. Frizzle's fifth graders were still comparing the numbers of freckles on their right arms when Mrs. Magee's champions had left for lunch.

To be continued in Sorting During the Flu Outbreak: The Reality of Sorting Small Sets

---------------

To learn more about other sorting techniques see Why Tailors Use Insertion Sort or Bullies, Bubble Sort, and Soccer Tickets.