[zasdffaa]

> sorting polygons correctly is inherently O(N^2), [...] because polygon overlap is not a transitive property (A in front of B and B in front of C does NOT imply A in front of C, due to cyclic overlap.)

Well ok but I don't get this:

> This means you can't use O(N lg N) sorting, which in turn means sorting 1000 polygons requires a million comparisons -- infeasible for hardware at the time

ISTM you CAN'T sort it full stop because of cycles - so what kind of sort (never mind O(N^2), any sort) can order cycles? They can't.

[dmbaggett]

Your intuition is correct. However, in the context of an O(N^2) comparison sort you can implement a tie-breaker check that at least ensures order stability between frames.