When would you ever want bubblesort? (2023)

On 8-bit and 32-bit microcontrollers (e.g. 8-bit AVR, 32-bit ESP8266/ESP32), Insertion sort is 6X faster than Bubble Sort on random data. I have tested this up to about N=1000.

Both Insertion sort and Bubble sort are O(N^2). Both are stable sorts. Insertion sort consumes only about 10-20 bytes more flash memory than Bubble sort. It's hard to think of situations where Bubble sort would be preferred over Insertion sort.

Shell sort is vastly superior if you can afford an extra 40-100 bytes of flash memory. (It's not too much more complicated than Insertion sort, but sometimes, we don't have 100 extra bytes.) It is O(N^k), where k ≈ 1.3 to 1.5. As soon as N ⪆ 30, Shell sort will start clobbering Insertion sort. For N ≈ 1000, Shell sort is 10X faster than Insertion sort, which in turn is 6X faster than Bubble sort. Unfortunately Shell sort is not stable.

Comb sort has a similar O(N^k) runtime complexity as Shell sort. But it seems slower than Shell sort by a constant factor. Comb sort is also not stable. I cannot think of any reason to use Comb sort over Shell sort.

Quick sort is not much faster than Shell until about N ≈ 300. Above that, the O(N*log(N) of Quick sort wins over the O(N^k) of Shell sort. But Quick sort is not stable.

Merge sort is stable and runs in O(N*log(N)), but it consumes an extra O(N) of RAM, which may be impossible on a microcontroller. You may be forced back to Insertion sort for a stable sort.

There is stable in-place merge sort, it runs in O(n*log(n)^2). It is about 3 times more complex than shell sort. I implemented it here https://github.com/thomasmueller/bau-lang/blob/main/src/test... (most sort algos you mentioned above are in the same direcory btw)

You didn't mention heap sort. A simple implementation, which doesn't do any method calls just like shell sort (also next to the merge sort above) is about twice as complex than shell sort.

Thanks for the reference to in-place merge sort. GitHub is having a lot problems right now, I cannot see your code. I will look at it when I get a chance.

I think I ignored Heap sort because it uses O(N) extra RAM, which is precious on a resource-constrained microcontroller.

Heap sort is in-place (and does not even need recursion, unlike quicksort). But yes, it is not stable, and usually slower than even shell sort (except for very large arrays).