# Sorting entities by Z in every call to Draw

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)$, but I'm 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?
-
I wouldn't worry about this until it becomes a problem, but once it has consider maintaining the list of entities on screen that have SpriteComponents (i.e. cache them) so that the Where isn't needed. Additionally in this scenario you probably could tell it to only sort when an item is Add/Removed from the screen which I'm guessing is a lot less frequent than the draw calls. –  Shelby115 Sep 18 at 15:14

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.