One solution to this problem is to cut the polygons into sortable sub-pieces. The most popular method for doing this is called Newell's algorithm, although modern computer graphics does not employ it.
@kavimehta Is there a crucial reason why modern computer graphics don't employ this? Seems like a reasonable choice to break the triangles into smaller polygons once the triangles can't be sorted.
This algorithm reminds me quite a bit of a very common problem in systems courses - deadlocks. Perhaps another approach rather than Newell's algorithm is to use one that resolves deadlocks?