The Vindication of Bubble Sort
As long, long-time readers know, I have a strong aversion toward bubble sort. Until recently, I would have loudly argued that there are no valid reasons to even teach someone bubble sort. The argument went something like this:
There is nothing good about bubble sort. It’s not intuitive or easy to understand, it’s not fast, it’s not memory efficient, it’s not conservative in terms of writes or reads. There’s nothing speaking for bubble sort.
I lament that we use bubble sort to teach algorithms, because it imprints all sorts of bad habits in students and some of them actually later go on and do these stupid things in the real world.
Every single case in which you may think bubble sort is a good idea, insertion sort is a better idea.
In other words, it’s not even a matter of tradeoffs, it’s that insertion sort beats bubble sort on every dimension. I still get pushback on this and it makes me unreasonably emotional.
Some people tell me bubble sort is more intuitive to them than insertion sort, but every time I hand them a few playing cards and ask them to sort them in their hands, they use insertion sort. Nobody would even think of using bubble sort.1 I speculate people remember bubble sort because the central mechanism is so weird. Keep swapping adjacent elements until sorted? That’s such an odd way to sort things that it sticks. It would have comedy value if it weren’t so sad. Now, insertion sort? So easy even a child could invent it. And they do.
So I thought I was on firm ground, stating there are no use cases for bubble sort. However, a few years ago a friend of mine pointed out they had found one.
When to Bubble Sort
The case was that a sequence was supposed to be sorted, but it wasn’t critical if it wasn’t. I.e. the more well-sorted the sequence was, the better, but everything would work okay-ish even with a random order.
The sequence couldn’t be sorted up-front for two reasons:
- This was a soft-realtime application, so at no point could the sequence be sorted without blowing several deadlines.
- The sequence itself changed and was replaced every now and then, so in the worst case, even if one spent the cycles sorting it, it could very well be thrown out the next thing that happens.
So my friend started thinking of ways of incrementally sorting the sequence. This can be done with conventional algorithms (e.g. quicksort), however, then we would need to keep track of how much is sorted between partial sortings. This gets doubly tricky when the sequence is modified between partial sortings.
You might sense where this is going.
This is the perfect use case for bubble sort.
The central part of the bubble sort is stateless and idempotent on a sorted sequence, but on an unsorted sequence it will always decrease its entropy. It gets even better when, as in this case, the application needs to regularly interate the sequence anyway. It could swap adjacent pairs as part of that iteration, at very little additional cost because the cache lines are already hot.
In practise, what my friend figured out was a virtually cost-free way to approach a sorted sequence, using bubble sort. I’m extremely impressed.
Postscript: The sarcastic cynic in me will still claim that oh so this one single use case you found for bubble sort is when you don’t actually need the result to be sorted? Great sorting algorithm you got there.
But obviously, that is a joke. I’m still impressed.