Re: more on stable sorting...
Re: more on stable sorting...
- Subject: Re: more on stable sorting...
- From: Chris Kane <email@hidden>
- Date: Sat, 7 Dec 2002 17:03:10 -0800
On Friday, November 22, 2002, at 03:57 AM, Chris Hanson wrote:
It's a little disturbing to me to hear people saying that NSArray's
included sorting methods aren't stable. I know they're not documented
as such, but I did write some unit tests that demonstrated they (at
least sort of) were...
Can someone from Apple make a definitive statement one way or the
other? (Not about what the docs say now, but about what the
implementation actually does today. I anticipate filing a feature
request, asking that the default sort be stable and be documented as
such in the future.)
Here is an authoritative answer for the records (though I don't want to
establish an expectation that authoritative answers are always going to
be available!):
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.]
Exposing more sorting possibilities has been on the table for quite a
while now, but there always seem to be more important activities that
get in the way of adding little bits-and-pieces of API to a release.
It is more likely that this would be exposed as a "stable sort"
possibility, rather than explicitly a "merge sort", though merge sort
would be the most likely candidate algorithm.
Chris Kane
Cocoa Frameworks, Apple
_______________________________________________
cocoa-dev mailing list | email@hidden
Help/Unsubscribe/Archives:
http://www.lists.apple.com/mailman/listinfo/cocoa-dev
Do not post admin requests to the list. They will be ignored.