Under the Bridge

Here’s an excellent article on how to do optimized NSArray sorting and NSMutable Array sorted inserts.

NSArray admits to sorts being a slow operation, and adds a method pair for comultive sorts using hints. This way the operation is done inO(P*LOG(P)+N) time, instead of O(N*LOG(N)). Where N is number of elements, and P is number of additions and deletions since the last sort. Unfortunately that do not work on NSMutableArray. So even if memory consumption will not hit the roof, release retain cycles will take it’s toll.

So why not add methods to find the insertion points, and insert new objects into already sorted NSArray and NSMutableArray object? Best case for inserting single elements should be O(LOG(N)^2), so lets hit that target. And on the way there, we will learn how to;

• Add functionality to standard classes using categories.
• Implement high performant Obj-C code for tight loops.

Good stuff, indeed. Here’s the code; take a look if you do Cocoa programming on either the desktop or iPhone!

h/t: LinkedIn’s Cocoa Touch!