Loop or sort for layered draw?

Question

Assuming a collection of objects, each of which needs to be drawn at a specific layer, at what point would it (or ever) be better to sort each object by layer rather than looping multiple times and drawing a layer at each pass? More importantly how would you arrive at this conclusion? Bonus points for a sort algorithm you would use if you would sort?

for (obj = each in collection) {
  for (i=0; i<=topLayer; i++) {
    if (obj.layer == i) {
      obj.draw()
    }
  }
}

/* vs. */

function layerCompare(obj1, obj2) {
  return (obj1.layer > obj2.layer)
}

collection.sort(layerCompare) 

for (obj = each in collection) {
    obj.draw()
}

Answer 1

If you loop through every layer and every object, that is O(m*n) where m is number of layers and n is number of objects. However, if you sort the layers ahead of time with something like quicksort, you can sort them in O(n*log(n)) and then draw them in O(n), yielding a total complexity of O(n*log(n) + n) = O(n*log(n)).

So in theory, its always better to sort them. In practice, you would have to benchmark.

EDIT: On second inspection, the cutoff is whether m < log(n). If the number of layers is less than the log of the number of objects, then you should do the double loop, otherwise sort them.

Answer 2

If your code is such that not many layers come and go, it makes vastly more sense to always keep your layers sorted. One such way to accomplish that trivially is to make a layer itself a drawable object that can contain objects. At this point, your layering is built into the recursive nature of the layer object itself.

Alternatively, you could just have a layer list which each layer being a single list of objects.