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.

Bullies, Bubble Sort, and Soccer Tickets

Bubble sort is a simple sorting algorithm. The algorithm repeatedly passes through an array, swapping adjacent elements that are out of order. As a result, larger elements "bubble" up to the end of the array, while smaller numbers "sink" down. This process continues until the array is sorted. Like insertion sort, bubble sort's worst case performance is O(N^2).

Peter had been in line for two hours when he felt the tap on his shoulder. He felt a pang of fear as he looked behind him. Terrible Todd glared angrily back. Then again, Terrible Todd always looked angry to Peter.

Terrible Todd was best known for his recent performance at the annual Alexandria area rock throwing contest. He was the first candle maker's apprentice to win the main event. His winning throw used a two hundred pound rock and the reverberation could be felt two miles away. Unofficially, he was also known for being a mean bully.

"Hi Todd." Peter meekly greeted him.

Todd grunted back and motioned Peter out of the way. Peter held firm. He refused to give up his place in line. Season ticket sales for the East Alexandria soccer team started in an hour. This year Peter was determined to get premium season tickets. He had his heart set on midfield.

"I am sorry, Todd. I was here first." Peter explained.

Todd looked Peter up and down. Then, with a louder grunt, Todd picked up Peter, turned, and set him down behind himself.

"Hey!" Peter cried, but Todd was already tapping the shoulder of the next person in line.

Peter fumed. This was not fair. Why should Todd get to go in front simply because he was larger? There were principles to these things.

As Peter ranted silently in his own head, he watched Todd slowly work his way up the line. One person at a time, Todd swapped places with smaller people. Todd’s advance was only halted when he reached Wren, the muscular blacksmith.

Then Peter felt another tap on his shoulder. Turning, he saw Big Jim. With a sigh, Peter stepped to the side and let Jim go ahead. Like Todd, Big Jim worked his way forward through the line. To Peter's pleasure Jim even moved in front of Todd to take the spot behind Wren.

Now Tiny Mike stood behind Peter. Peter tried to glare at Tiny Mike, making it clear that Mike was not moving ahead. Mike did not even try.

This process continued for the next hour. Every time a larger person found themselves waiting behind a smaller person, there was a polite tap on the shoulder and a switching of positions. Each time Peter moved back in the line he felt a little more demoralized. He was not a big person, and thus he found himself unable to swap with anyone. By the end of the hour the entire line was sorted by size, and Peter was near the back. Discouraged, Peter left the line and returned to the library.

As Peter sulked behind the library's counter, he remembered that now tickets were also available by pigeon message. He hurriedly filled out the form, requesting "Best Available". The pigeon flapped away, carrying Peter's only hope for reasonable seats. Ten minutes later, the pigeon returned with a confirmation of second-row, mid-field. Peter was thrilled. He must have gotten his tickets before even Big Jim.

That day Peter learned two important lessons. First, bubble sort is great for bullies. Second, standing in line was not worth it in the age of near-instantaneous pigeon-based ordering.

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

Read more about sorting algorithms with Merge Sort and Lines of Kindergarteners, Why Tailors Use Insertion Sort, or Sorting During the Flu Outbreak.