If you're happy with your engine's behavior and performance than feel free to disregard. But if it is something you want to noodle on...
> I dug around and found an article that said the time complexity (for topological sorting of sprites) was O(N^2)
Topo sort in general is O(V + E) where V is the number of vertices in the graph and E is the number of edges. If you consider your set of sprites a graph with an edge between every pair of sprites, then it does become O(N + N*N) which is O(N^2).
If the only way to get topo sort to work is by treating the sprites as a fully connected graph, then it's not the right approach. Topo sort really only makes sense when the number of edges between nodes is relatively low. You'd be better off using quicksort which is O(N log N).
However, since you are going to be resorting the same data each frame and most sprites stay in the same order, what you want is a sorting algorithm that works well on mostly-sorted data. In that case, I suspect insertion sort is what you want. It will roughly behave like O(N) when the data is mostly sorted.
Alternatively, you could look at bucket sort. While your sprites can be freely positioned with floating point coordinates (which makes pigeonhole sort a poor fit), they still fall within a known finite range, and bucket sort is designed to handle that case.
It's a fun problem to think about. [1] I don't have a computer science background, so I appreciate you bridging the gaps in my knowledge.
I mostly understand what you're suggesting (I'd need to read up on how each individual algorithm works at a low level). It's true that most of the sprites would remain in the same order and in theory it would be worth looking into this (it may benefit low powered machines -> widen the potential market).
However, there are other limitations with the framework I'm using that make me pause. I'm using OpenGL and Vertex Buffer Objects (semi-dynamic Vertex Arrays, ie. a std::vector<> of vertex information that the GPU can store locally). When a vertex array is updated, the entire array must be resent to the GPU, or alternatively one can do individual range updates (which... are not working at the moment). There can be so many sprites on the screen that a full update would cause the FPS to drop (learned this by example). And since CPU -> GPU communication is so costly, I assume hundreds of individual updates would also drop the FPS.
With my custom depth maps for each sprite, the vertex array only needs to be sent once. (Side note: the world is broken into 40x40 chunks)
> If the only way to get topo sort to work is by treating the sprites as a fully connected graph, then it's not the right approach.
One trick the OpenRCT devs did was split the screen (or scene?) into 64 pixel wide vertical strips. Though they still said the performance was O(N^2) for each strip.
[1] I am content with the engines performance for now. Last I tested I, a very dense scene ran >165 FPS on a medium performance GPU.
> I dug around and found an article that said the time complexity (for topological sorting of sprites) was O(N^2)
Topo sort in general is O(V + E) where V is the number of vertices in the graph and E is the number of edges. If you consider your set of sprites a graph with an edge between every pair of sprites, then it does become O(N + N*N) which is O(N^2).
If the only way to get topo sort to work is by treating the sprites as a fully connected graph, then it's not the right approach. Topo sort really only makes sense when the number of edges between nodes is relatively low. You'd be better off using quicksort which is O(N log N).
However, since you are going to be resorting the same data each frame and most sprites stay in the same order, what you want is a sorting algorithm that works well on mostly-sorted data. In that case, I suspect insertion sort is what you want. It will roughly behave like O(N) when the data is mostly sorted.
Alternatively, you could look at bucket sort. While your sprites can be freely positioned with floating point coordinates (which makes pigeonhole sort a poor fit), they still fall within a known finite range, and bucket sort is designed to handle that case.