Well, the input array is of course O(n) (actually omega n), the output array could be basically anything, the algorithm is quadratic.
I quite simply can't come up with a test case that kills it, even if I start adding sprites like crazy - my hand gets tired of clicking the "add sprite" button in the editor WAY before profiling results show it to be significant.

Long text balloons were a good example of lotsa rects, and essentially w/wjp's patch they are fixed.

So, I'd *really* use the ostrich algorithm here.

Suggestions to correctly estimate the threshold where a single giga rect is more convenient are really welcome, though - I can't think of any myself (and creating a really tangled up test case by hand simply doesn't get nowhere near there).