Sorting sprites

Split by category

More often than not you only care whether certain kinds of objects are in a given order (player, enemies, items, bullets, etc.) but don't care about the order between objects of the same type. In this case you can have separate lists for each kind of object and go through the lists in the order you want.

The downside is having to maintain multiple lists. On the other hand, this kind of split is also useful to speed up collision checks (only go through the list you're interested in) so it's always worth considering.

Keep objects sorted

This method is mostly useful when there's actually depth like in an isometric game or a beat'em-up.

In short: keep the objects themselves sorted by depth and sort again on every frame (you can use a linked list to avoid moving things around, though it can be hard to get right). The appeal of the idea is that objects rarely swap places across frames, so you can use something like insertion sort which is simple and will breeze through the list most of the time since it's already sorted (or nearly sorted).

The only issue is adding new objects, but just append them at the end of the list and let the sort do its job. The occassional outlier isn't much of a performance hit compared to the overall savings.

Sort as you insert

If you absolutely need per-sprite depth but don't want to mess with sorting objects (or even need a single object output multiple sprites each with its own depth), you can try this.

Instead of drawing a sprite directly, put each one in a list. You sort them the moment each sprite is inserted. One approach is as follows:

  1. Reserve a free slot at the end of the list
  2. If it isn't the first slot and the previous slot's sprite is deeper:
    1. Move previous slot's sprite to current slot
    2. Go back one slot and return back to step 2
  3. Otherwise:
    1. Insert the new sprite into the current slot
    2. We're done here

Another approach could be to do a binary search to find the appropriate spot to insert.

Either way, this will leave sprites sorted from front to back. After every sprite has been inserted you can draw them in the order they were left behind in the list.