You can construct an NSOrderedSet* from your array; using +orderedSetWithArray: will preserve the array's existing order. If it's not already in the correct order, you can't sort the set directly, so there's little point in using an ordered set, but you can easily construct a regular NSSet and sort that into another array, using -sortedArrayUsingDescriptor:, or even better allObjects, followed by any of NSArray's sorting methods.
On the other hand (it's possible I'll get some nasty comments about this, but...), since NSArray and NSSet seem to be built on top of the same hash table functionality, you could just do this:
id newObj = // Acquire new object from wherever
while( newObj ){
if( ![arrayImConstructing containsObject:newObj] ){
[arrayImConstructing addObject:newObj]
}
newObj = // Acquire next object
}
This is basically what an ordered set has to do when you construct it anyways, and it's quite likely that your array is small enough (if you're putting it into a UIPicker) that you won't notice a performance difference at all. Still, measure the two, and then decide.
*NSOrderedSet is available on iOS > 5.0 (or OS X > 10.7).