11

Are the sorting algorithms used by the various sorting methods in NSArray stable? (As in are they "stable sort" algorithms, where items with the same sort key have their relative orders preserved.)

StCredZero
  • 464
  • 3
  • 13
  • 6
    @TDeBailleul "Giving it a try" is not really helpful in this case. The sorting may be stable in certain cases, but not others, depending on the size of the data, how the array was constructed, etc. – omz May 07 '12 at 18:28
  • Ok, I thought the behavior was always the same. Good to know. – Titouan de Bailleul May 07 '12 at 18:33
  • If it is not stable in one single case, then it is not stable. So "giving it a try" _is_ helpful. – gnasher729 Jan 24 '15 at 22:24

3 Answers3

18

Stable sort is not guaranteed unless you use NSSortStable. From the documentation on NSSortOptions:

NSSortStable

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.

If you need to guarantee a stable sort, try something like:

[array sortWithOptions:NSSortStable usingComparator:^NSComparisonResult(id obj1, id obj2) {
    return [obj1 compare:obj2];
}];
wxactly
  • 2,400
  • 1
  • 26
  • 42
  • `(void)sortWithOptions:usingComparator:` works for mutable arrays... there's also `(NSArray *)sortedArrayWithOptions:usingComparator:` if that floats your boat – wxactly Jan 24 '15 at 22:14
7

The only "official" answer I've found about this is a 2002 mailing list post by Chris Kane from Apple:

The stability of NSArray/NSMutableArray's sorting methods is undefined, so you should anticipate that they are unstable. Being undefined, the situation may also change from release to release, though I don't (myself) anticipate that this is likely. The current implementation uses quick sort, a version of the algorithm nearly identical to BSD's qsort() routine. A bunch of experimentation found at one point that it was hard to do better than that for the general types of data we through at the tests. [Of course, if one has additional information about the data being sorted, one can use other algorithms or modifications which help that case.]

I don't know whether this is still true, given how old the post is, but it's probably best to assume that NSArray's sorting methods are not stable.

omz
  • 53,243
  • 5
  • 129
  • 141
4

In the doc, no details are given as to the final order of identical items.

Therefore, I feel making any assumptions about the order would be a bad idea. Even if you determine experimentally what the order is, this could change based on the number of items in the array or which version of iOS runs the sort.

For me, I would stick with the promises provided by documentation.

Jeffery Thomas
  • 42,202
  • 8
  • 92
  • 117
  • I wouldn't trust it even if I had tested it thoroughly, Apple might change the used algorithm(s) in the next version rendering any tests pointless and might cause some strange bugs. – JustSid May 07 '12 at 18:30
  • 4
    The documentation *does* specify, it's just buried behind the documentation for `NSSortOptions`: https://developer.apple.com/library/ios/#documentation/Cocoa/Reference/Foundation/Miscellaneous/Foundation_Constants/Reference/reference.html#//apple_ref/doc/c_ref/NSSortOptions – wxactly Apr 14 '13 at 03:56