How to keep an array sorted

Question

I'm refactoring a project that involves passing around a lot of arrays. Currently, each method that returns an array sorts it right before returning it. This isn't ideal for a couple reasons -- there's lots of duplicated code, it's inefficient to sort an array two or three times, and it's too easy to write a new function but to forget to sort the array before returning it.

I'm looking for a way to guarantee that the array always kept in alphabetical order. My current thought is to subclass NSMutableArray and/or NSArray to create an alphabetized array class. I would need to override all of the methods that create or modify the array to call super and then sort itself.

Does this sound reasonable, or is there a better approach?

EDIT: Since performance issues have been mentioned, I'll include the relevant information from my project. Speed is not an important concern. The whole process only takes a few seconds, and the tool is only used every so often. So simplicity and obvious correctness is more important.

Also, the use case for arrays is specific. When an array is returned, the caller always accesses every element in the array at least once.

Answer 1

A balanced binary tree is the standard and efficient way to keep items sorted. Almost any way to do random access with a plain array will be slow. A skip list is also efficient and you may be able to add the functionality to the array class.

Answer 2

Check out CHDataStructures. It's a framework that has a lot of self-sorting datastructures, like balanced binary trees and whatnot.