Why Sorting is Taught in Algorithms Classes
This blog explains why sorting is taught in algorithms classes, not because it is an important algorithm to learn to implement, but because it is a simple and easy to motivate example of different algorithms for accomplishing the same task.
Morgan McGuire
Roblox Chief Scientist U.Waterloo & McGill Prof. Known for NVIDIA, Unity, Graphics Codex, Markdeep, G3D, Skylanders, E Ink, Titan Quest, Williams
-
It wasn't until I'd *taught* algorithms a few times that I finally understood why sorting is in the CS curriculum. Unfortunately, most curricula don't explain this!
— Morgan McGuire (@CasualEffects) June 23, 2023
It is NOT because sorting is an important algorithm to learn to implement... https://t.co/9Us0XkfCzO -
It isn't even because programmers will need to know the tradeoffs between different sorting algorithms to choose one (99% of the time)...
— Morgan McGuire (@CasualEffects) June 23, 2023 -
We teach sorting in algorithms classes because it is a simple and easy to motivate EXAMPLE of different algorithms for accomplishing the same task. The solution isn't the point in the classroom. The problem is the point...
— Morgan McGuire (@CasualEffects) June 23, 2023 -
By using different sort algorithms as a running example, we can cover ideas such as:
— Morgan McGuire (@CasualEffects) June 23, 2023
- Asymptotic analysis
- Space vs. time tradeoffs
- Best case vs. worst case vs. expected case behavior
- Functional vs. imperative implementations
- Explicit stack vs. recursive implementations pic.twitter.com/TZKQjhz90O -
- Stable vs. unstable
— Morgan McGuire (@CasualEffects) June 23, 2023
- Adversarial cases
- Concurrency
As a bonus, we can also point out that if you give your algorithm a cool name like "QuickSort", then generations of programmers will naively assume that it is the fastest sorting algorithm and use it... -
Unfortunately, what we've also done by using this convenient example of sorting and its many possible solutions is created generations of programmers who mistakenly think that sorting is an important open problem or something that matters for performance very often. pic.twitter.com/hhSiQ9syIU
— Morgan McGuire (@CasualEffects) June 23, 2023 -
As a professor, scientist, programmer, game developer, etc. what sorting algorithm do I use?
— Morgan McGuire (@CasualEffects) June 23, 2023
WHATEVER SORT IS IN MY STANDARD LIBRARY
... pic.twitter.com/PK3ecHBGsh -
Very, very, very occasionally, sorting performance or behavior matters so much for a specific application that I need think about it for a total of five minutes.
— Morgan McGuire (@CasualEffects) June 23, 2023
And then I use:
the radix sort THAT IS IN MY STANDARD LIBRARY.
... -
That said, heap sort in C is my favorite sort, just because it has a wicked cool implementation. But this is like Rubik's Cube or my favorite ice cream: it is neat, I like it, and it has zero to do with actual software development.
— Morgan McGuire (@CasualEffects) June 23, 2023
... -
In conclusion, the point of the sorting lectures you had in college was the lessons you learned along the way, not the sorting. I'm really sorry we didn't tell you that at the time! pic.twitter.com/HDQuyVuJHb
— Morgan McGuire (@CasualEffects) June 23, 2023