Remix.run Logo
GuB-42 18 hours ago

There is "early exit after the first swap", which actually makes his algorithm closer to insertion sort than bubble sort. If the list couldn't change between each pass, it would be a very inefficient insertion sort in O(n^3) as you are constantly scanning the part of the list that is already sorted.

But this is a case where theory doesn't count as much as having an acceptable result. It is typical in video games, if it plays well and looks fine, who cares if it is incorrect. Here I guess that sometimes a sprite appears on top of another sprite when it should have been behind it, because of the early exit, but while playing, it turned out not to be noticeable enough to change the algorithm.