Sorting Algorithms and Piles of Paper
I’m the TA for an algorithms class, and one of my duties is to alphabetize the students’ homework. Students turn in each question separately, which means I have to alphabetize 3 distinct piles of about 100 papers each.
As this is an algorithms class, it seemed like a natural opportunity for an experiment: what sorting algorithm would alphabetize the piles fastest? I decided to test 3 algorithms (which eventually turned into 4, due to the failure of heapsort):
- Quicksort: average runtime O(n log n), worst-case runtime O(n^2)
- Insertion sort: average runtime O(n^2), worst-case runtime O(n^2)
- Heapsort: average runtime O(n log n), worst-case runtime O(n log n)
- Merge sort: average runtime O(n log n), worst-case runtime O(n log n)
I initially expected that quicksort would win the day, due to its low overhead and generally good performance on computers. The surprising results are below!
- Quicksort: 21 minutes
- Insertion sort: 19 minutes
- Heapsort: I had to give up halfway through, because the heap tree got larger than my carpet.
- Merge sort: 23 minutes
So what gives? I have two theories, both of which I find compelling:
- Insertion sort has lower cognitive overhead than the others. It’s the “natural” algorithm: one by one, just stick papers in the already sorted pile where they belong. For the other algorithms, I had to spend time at each step figuring out what to do next.
- Insertion sort is slow on computers because inserting into the middle of an array is slow: you have to shift every element over by one. However, inserting into the middle of a stack of papers is a constant time operation: just stick the paper in there! Finding where to insert the next paper was also relatively quick, because I could estimate the middle of any pile quickly, and thus perform a binary search in O(log n) time. So, the algorithm was actually O(n log n) with my fancy new data structure!
I did this as an experiment for myself, but it’s a good reminder for my students: while we focus on asymptotic runtimes in school, in the real world it’s usually better to look at benchmarks for realistic data sets. By benchmarking, I was able to save myself 2 minutes of work for every question that I have to grade!