Documentation for NSSortStable is ungrammatical -- what is it trying to say?

Question

I have an array I would like to sort, and since Blocks are this year's "black", I was looking at

- (void)sortWithOptions:(NSSortOptions)opts usingComparator:(NSComparator)cmptr

I looked up what sort option to use and the NSSortStable documentation said:

Specifies that the sorted results should return compared items have equal value in the order they occurred originally.

If this option is unspecified equal objects may, or may not, be returned in their original order.

I haven't had enough coffee to understand what its saying, the first sentence isn't even grammatically correct.

Can anybody translate into English for Dummies?

Answer 1

NSSortStable specifies that if two objects compare equally, their order should remain the same.

For example, let's consider the following:

NSMutableArray *array = [NSMutableArray arrayWithObjects:@"one", @"two", @"three", @"four", nil];
[array sortWithOptions:0 usingComparator:^NSComparisonResult(id obj1, id obj2) {
    if ( [obj1 length] < [obj2 length] )
        return NSOrderedAscending;
    if ( [obj1 length] > [obj2 length] )
        return NSOrderedDescending;
    return NSOrderedSame;
}];

If you don't specify NSSortStable, the sorted array may be either (one, two, four, three) or (two, one, four, three) as one and two have the same length. Both results are accepted. This allow the sort algorithm to perform (a little) faster.

When specifying NSSortStable, the objects that compare equally must be returned in their original order (i.e. first one, then two).

Answer 2

A stable sort is one that preserves the order of elements as much as possible.

For instance, if you're sorting on last names, then a stable sort would keep first names in the same order as they originally appeared in the container. That is, if we had:

Bob Smith
Tom Jones
Dave Smith
Fred Smith
Al Jones

It would sort to

Tom Jones
Al Jones
Bob Smith
Dave Smith
Fred Smith

Note that Tom is still above Al, and Bob is still above Dave who is still above Fred.

An "unstable sort" would not attempt to preserve the secondary ordering, and as a result can run slightly faster.

http://en.wikipedia.org/wiki/Sorting_algorithm#Stability