When would you ever want bubblesort?
There are few universal rules in software engineering. But "don't use bubble sort" comes close.
Donald Knuth wrote that bubble sort "seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems".[reference:0]
Knuth has been wrong before.[reference:1] Let's see if he's wrong here.
The small array case
Bubble sort is faster than quicksort or mergesort for very small arrays.[reference:2]
This matters because most fast sorting algorithms work recursively. When you apply quicksort to 2^20 random integers, you eventually end up sorting 2^17 subpartitions of 8 integers each.[reference:3] Switching to bubble sort for those tiny subpartitions would be a nice optimization.
Production sorting algorithms do use hybrid approaches. But they overwhelmingly use insertion sort instead.[reference:4] Insertion sort is very fast for small arrays and better at using the hardware.[reference:5]
On some very particular hardware, bubble sort still ends up better. There's an NVIDIA study that used it.[reference:6] But you probably don't have that hardware.
The real-time rendering case
Game development has a situation uniquely suited to bubble sort.[reference:7]
Two properties make it work:
Each individual step is very fast and easily suspendable.[reference:8]
Each swap leaves the array more ordered than before. Other sorts can move values away from their final positions in intermediate stages.[reference:9]
Say you have objects on a screen where some occlude others. You want to render objects closest to the camera first. That way you can determine which objects they hide and save time rendering those objects.[reference:10]
There's no correctness cost for rendering objects out of order. Just a potential performance cost.[reference:11] The more ordered the array, the happier you are. But you can't spend too much time sorting because you have strict real-time constraints.[reference:12]
Bubble sort works well here.[reference:13] You can run it a little bit each frame and get better ordering than when you started.
The animation case
Here's a fun one.
You have a random collection of randomly colored particles. You want to animate them sorting into a rainbow spectrum.[reference:14]
If you make each frame of the animation one pass of bubble sort, the particles will all move smoothly into the right positions.[reference:15]
This might not actually be done in practice. Running a better sort to calculate each particle's final displacement and animating them moving directly would probably look smoother.[reference:16] But the bubble sort approach is elegant in its simplicity.
The bottom line
Three niche use cases for bubble sort.
You'll probably never need it.[reference:17]
But if you're working with tiny arrays, rendering 3D objects in real time, or making a cool sorting visualization, bubble sort might just be the right tool.
Sometimes the "wrong" algorithm is exactly what you need.
Source: https://buttondown.com/hillelwayne/archive/when-would-you-ever-want-bubblesort/