Sorting During the Flu Outbreak: The Reality of Sorting Small Sets

When selecting an algorithm, it is important to understand the context in which it will be applied. An algorithm's computational complexity only tells part of the story. Other factors to consider include: the size of the data, the existence of other constraints, and additional problem structure that can be used. For example, bubble sort is a reasonable algorithm to use for a very very small amount of data that is almost in the correct order.

For years, Mrs. Magee's kindergarten class won every sorting competition in the kingdom. The powerful combination of constant practice and the merge sort algorithm made them unstoppable. Records were decimated weekly. Soon it was no longer enough for her class to win; they had to finish sorting themselves in less than half the time as their competition. The only true victory was total domination.

Thus, it came to pass that Mrs. Magee became overconfident in the ability of her class. She firmly believed that her kids could win regardless of the situation, and she had no problem explaining that to everyone she met.

Then, in January, the flu hit. Almost all of Mrs. Magee's class was out sick, leaving just three students in class. It was under these conditions that Mr. Wallace's second graders challenged her to a sorting competition. He also had three healthy students, so the classes were equally matched. But his class only understood the lesser "Bubble Sort" technique. His search could take O(N^2) time!

As soon as the moderator shouted "Go", Mrs. Magee's class split into two groups. One group had two students, and the other had only one student. The merge sort had begun.

In contrast, Mr. Wallace's students looked at each other. Billy and Sue did a quick comparison in their head and swapped places. All three were now in the correct order.

"No!'" wailed Mrs. Magee, but it was too late. The competition was over.

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

Read about the skill of Mrs. Magee's class in Merge Sort and Lines of Kindergarteners. Or read about other sorting algorithms in Why Tailors Use Insertion Sort or Bullies, Bubble Sort, and Soccer Tickets.

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.