If we utilize integers, we may end up with some issues with rounding, since items are rarely some integer distance away. Thus, two objects that are very close together depth-wise may end up in front or behind each other due to floating point imprecision and other such things. I believe this is what causes the phenomenon known as Z-fighting.
From Wikipedia: "Another technique that is utilized to reduce or completely eliminate Z-fighting is switching to a logarithmic Z-buffer, reversing Z." (idea being closer to 0 = more precision).
How would we sort n triangles in linear time? Or do we say it's O(n) simply by going through each triangle, replacing pixels as necessary when we find a triangle that is closer (in turn not actually sorting the triangles)?
If I understand correctly, sorting the triangles is unnecessary. No matter the triangle order you will produce an image following Z-Buffer rules. Different orderings may produce slightly different images because of tie-breakers. Professor refers to something here as brute force. Would that be the "lazy" nature of not needing to sort the triangles?