The Vindication of 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:

1. This was a soft-realtime application, so at no point could the sequence be sorted without blowing several deadlines.
2. 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.