In a graphics processing pipeline 1, a primitive depth sorting stage 9 is arranged prior to the rasterization stage 3 and rendering stage 6. The primitive depth sorting stage 9 operates to sort successive sub-sets of primitives in a stream of primitives 2 received by the graphics processing pipeline 1 based on their depth values. The so-sorted primitives are then output from the primitive depth sorting stage 9 in their sorted depth order to the rasterizer 3. This makes the depth test stages 4, 13 of the graphics processing pipeline 1 more efficient in their hidden surface removal operations, because the primitives entering the rasterizer 3 will be in depth order.