4 ms·
It's good when there are a lot of elements off by a short distance in a mostly sorted list. The go-to use case that I've seen is depth sorting for 3D rendering
by taneq 6y ago
It's good when there are a lot of elements off by a short distance in a mostly sorted list. The go-to use case that I've seen is depth sorting for 3D rendering on really low end hardware. Polygons usually don't move much in the Z-order each frame, so you run a few passes of bubblesort per frame for a good-enough linear-time sort.
- ogogmad 6y agoDo you know how it compares to insertion sort, which is also fast on nearly sorted lists?
- NortySpock 6y agoAlso, two passes of cocktail-shaker sort (back and forth bubble sort) would guarantee that the top and bottom z-order would be correct, which would probably be good enough to keep really obviously bad z-ordering at bay. Like you say, when it's already partially sorted and you're just having to maintain a slowly-updated list, a single partial-sort pass per frame could be quite enough to maintain a good-enough ordering of a list.