> 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.