What sort function is used in NSArray?

Question

This is really a three-part question, but I've answered the first question myself:

I'm working on the iPhone, with many objects (up to 200) on the screen. Each object needs to look if it's overlapping other objects, and act accordingly. My original naive implementation was for each object to run through the list of each other object to check their bounding boxes (using CGRectInsersectsRect).

So my question (and answer) is what's a better method? My new implementation is to sort the array every frame using an insertion sort (since the data will be mostly sorted already) on the y-position of each object, then check only the nearest object on either side of the one searching, to see if it's in range vertically, then check horizontally.

First question: Is insertion sort the method I want to use for an array of objects that tend to move around randomly but only to a small extent so they mostly stay in order based on the last frame? Also: what sort algorithm does the NSArray use when I call

- sortedArrayUsingSelector:

I would sort of assume that it uses a quick sort, since it's the most useful in the general case. Does anybody know if I'm wrong? Does anybody know if I can change the sort method or if I will have to write my own sorting function?

Second question: is there a function for retrieving items from a sorted array using a binary search, rather than the naive approach that I assume is used by

- indexOfObject:

or would I have to write my own?

Answer 1

NSArray uses many different data structures internally depending on how many objects are in the array. See a Peter Ammon blog entry for more information. But basically this means you can't expect a certain kind of sort to happen. Sometimes it is worth it to write your own array implementation using C arrays so you can control the sorts yourself.

There are definitely much faster ways to implement collision detection. Look into Bounding Volume Hierarchies like KD Trees or similar.

As far as I know indexOfObject: is the only way, but it's potentially not as dumb as you think. Everything is hashable for NSDictionary so they can use some of those smarts in NSArray.