The current Dr. Touch Part that I am working on for my store is about quickly clustering POIs if they would be too close together on a MKMapView. For this purpose I need to calculate distances between all annotation pins and add to this the distances to all newly found clusters. Currently this involves resorting the whole list of distances multiple times. So I put my thinking hat on and built this category extension for NSMutableArray to add numbers of objects in the correct place according to the specified sort order.

To cut down on search time for the insertion point I am using a “divide an conquer” approach. Split the search range in half and check if the value at this index is bigger or smaller than the one I am trying to insert. Continue to divide until the length of my search range is 0. At that point I have found the appropriate place for the insertion.

This approach means that for 1000 values/objects in the array only 10 comparisons are necessary. This is most likely way less than if you are constantly creating sorted copies of the array with one of the three standard sorting methods.