# Sorting entities by Z in every call to Draw

I'm using XNA (Monogame) in C#. My implementation contains a SpriteComponent class which has a Z property; I use this to determine the order in which to draw my entities (higher Z = drawn on top). It's a simple integer.

What I'm worrying about (premature optimization, I suspect) is the runtime complexity of the function which gets the list of all the SpriteComponents to draw, in order of their Z attribute:

List<IEntity> entitiesToDraw = currentScreen.Entities
.Where(e => e.HasComponent<SpriteComponent>())
.OrderBy(e => e.GetComponent<SpriteComponent>().Z)
.ToList();


From what I've read, OrderBy uses QuickSort, which is O(n log n). Not sure about Where.

I can reasonably assume:

• 1000+ entities can concurrently exist
• 90% or more of entities have a SpriteComponent in them
• Changing the Z of a sprite happens fairly infrequently for most sprites

My questions are:

• If so, how can I reduce the runtime complexity, and/or cache the results reliably?
-
You can retag your own question at any rep by editing it. I've added the tag for you, though. –  Bobson Nov 29 '12 at 14:36

Where method (if applied to IEnumerable<T>) is O(N) operation, and it's a lazy operation so it will do the filtering while consumer reads the result.