Comment by dmbaggett

I doubt it. One observation is that polygons can experience cyclic overlap, so A > B and B > C does NOT imply A > C. This transitivity property is required for O(N lg N) sorting algorithms. And note that even with Crash 1 polygon counts, O(N^2) is > 1000^2 -- way too huge for a 33Mhz processor.

However, the way I did it was to precompute the sort order of the polygons ahead of time and store periodic key frames (the complete sorted list) along with diffs. These diffs were generally very small, meaning your intuition that not much changes from frame to frame is a valid one. The problem is without the runtime oracle telling you which polygons move from frame to frame, it seems hard to exploit this property.

Another issue with approximate polygon sorting methods like bucket sorting is that the sort isn't terribly stable from frame to frame, so you get the annoying flickering effect that you see so often in PS1 games, as a pair of polygons alternates between relative sort order as you move around.