PrimaryFeather/Starling-Framework — pull request #304 by tconkling (2013-03-12 23:27:38+00:00)
Title: DisplayObjectContainer.stableSortChildren

Hey Daniel -

This pull request adds a "stableSortChildren" method to DisplayObjectContainer, which is useful to prevent flickering when depth-sorting children who have the same depth value (the AS3 Vector.sort algorithm is, unfortunately, not stable).

I used the insertion sort algorithm for the implementation (http://en.wikipedia.org/wiki/Insertion_sort). Insertion sort doesn't have the best *theoretical* runtime performance, but in practice it works very well for display object depth sorting: after the first sort of a given DisplayObjectContainer, subsequent sorts will generally be close to O(n) (because most displayObjects won't be out of order after just a single frame). It also does the sort in-place, so there's no extra allocations happening.