Hacker News Reader

Comment by phamilton | Hacker News Reader

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.

View on HN

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

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.

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.

That's interesting. I never considered this before. I came across this years ago and settled on insertion sort the first time I tried rendering a waterfall (translucency!). Will have to remember bubble sort for next time

Reply on news.ycombinator.com