Firstly I define a render single queue object (CRenderQueue) which does an index sort on the objects inside it (not sorting the render-queue items but the indices to each item in the queue). These are maintained across frames to take advantages of temporal coherence (which is further exploited by using an insertion sort).
2 of these combine to make a CRenderQueueSet object in which one render queue is for opaque objects and the other for alpha-enabled objects.
In a basic scene with shadow mapping there are 3 render-pass types: Ambient/non-shadow-casting lights, shadow-map generation, and applying shadowed lights to objects (one extra pass per shadow).
The basic rule of thumb is that sorting needs to be done once per cull phase.
For the ambient and shadow-application phases the same objects will be drawn, so culling only happens once between the two stages, and thus sorting only happens once.
Then for each shadow you apply to objects, different objects will be culled on a per-light basis, so sorting also happens once for each light.
After culling (for any phase), the remaining objects are passed a CRenderQueueSet and so they can themselves to either the opaque render queue or the alpha-enabled render queue.
When submitting data to a render queue the objects need to know how to create a render-queue item, which requires that they know what type of render is being made (normal render or shadow-map-creation render, etc.)
This information is passed when the model is asked to submit itself to the render queue and it uses it in a simple switch case which selects the appropriate shader for that type of render and supplies that, along with other necessary information, to the render-queue item for the render queue(s).
A keen observer will then note that if they are only added to the render queue and sorted once, their shaders will change between the ambient pass and the shadow-map-application pass(es). Since shaders are very important for sorting, shouldn’t they be resorted?
This is true, but they will all change in the same way. That is, all shaders that had hemisphere lighting enabled and neither lights nor shadow-mapping enabled for the ambient pass will be permutated into the same shader when all of these are disabled or enabled for the later shadow-map-application pass(es). In other words, they all changed their shaders, but have remained implicitly sorted anyway.
In all cases, each render-queue remains across frames. Its clear function simply sets m_ui32Total to 0UL. The sorted indices stay sorted.
After adding back all the objects for the next frame, the objects will likely still be rendered in the same order as last frame and the insertion sort will quickly verify that.