[phamilton]

This feels similar to when I heard they use bubble sort in game development.

Bubble sort seems pretty terrible, until you realize that it's interruptible. The set is always a little more sorted than before. So if you have realtime requirements and best-effort sorting, you can sort things between renders and live with the possibility of two things relative close to each other appearing a little glitched for a frame.

[8n4vidtmkvmk]

I thought it was insertion sort? Works well on nearly sorted lists.

[phamilton]

That's a different problem. To quickly sort a nearly sorted list, we can use insertion sort. However the goal is to make progress with as little as one iteration.

One iteration of insertion sort will place one additional element in its correct place, but it leaves the unsorted portion basically untouched.

One iteration of bubble sort will place one additional element into the sorted section and along the way do small swaps/corrections. The % of data in the correct location is the same, but the overall "sortedness" of the data is much better.

[chipsa]

Quick sort usually uses something like insertion sort when the number of items is low, because the constants are better at low n, even if O(n) isn’t as good.