No one mentioned one of the most important things: You don’t sort the renderstates (or whatever object you put into your render queue) directly; you sort the indices to that list.
Copying around objects wastes time. Only copy the 32-bit indices and use that to draw in sorted order.
L. Spiro
^This^.
In my renderer, from a list of "items" that need to be drawn, I've got a function that generates a list of sort-key/index pairs. This second list can then be sorted (I use a radix sort for large lists) by itself, which is faster due to the amount of memory that has to be moved around being lower.
To render, I can then either submit the original list and the list of sorted indices together (where the index list will be iterated linearly, and used to randomly iterate the original list), or, I can use the indices to re-order the original list and then submit a sorted version of the original list by itself.
