CODEWITHSUNDEEP
iosobjective-ccocoasorting
P. Unto
P. Unto

Reputation: 246

What kind of sort does Cocoa use?

I'm always amazed by the abstractions our modern languages or frameworks create, even the ones considered relatively low level such as Objective-C/Cocoa.

Here I'm interested in the type of sort executed when one calls sortedArrayUsingComparator: on an NSArray. Is it dynamic, like analyzing the current constraints of the environment (particularly free memory) and the attributes of the array (length, unique values), and pick the best sort accordingly, or does it always use the same one, like Quick or Merge Sort?

It should be possible to test that by analyzing the running time of the method relatively to N, just wondering if anyone already bothered to.

Upvotes: 1

Views: 75

Answers (1)

gnasher729
gnasher729

Reputation: 52602

This has been described at a developers conference. The sort doesn't need any memory. It checks if there is a sorted range of numbers at the start or the end or both and takes advantage of that. You can ask yourself how you would sort an 100,000 entry array if the first 50,000 are sorted in descending order.

Upvotes: 1

Related Questions