You can bound polygon sorting by looking at the closest and furthest points from the camera for each polygon. This get's tricky if the polygon is perpendicular to the camera, but avoiding O(n^2) in the general case is huge.

Z-Buffer's are still a major advantage.