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.