What is the time complexity of (large O) sortedArrayUsingComparator? IOS / OSX

Question

I need to know the time complexity of sortedArrayUsingComparator from the NSArray class. The source would be great, since I most likely mentioned this in my thesis. I am sorting an array of locations by distance to the current location.

The only answer I could find was the one who said it was at least T (n) = O (n), but probably T (n) = O (n log n)

How do I know for sure?

Answer 1

The actual study of NSArray time sorting corresponds to O(n*log(n)) .

See blog post

Note that the comment has a sorting method (PS9110), which is O (n), but is patented and patented. The method is quite interesting.

Answer 2

Well, to sort an array, you need to at least take a look at each element, which is undoubtedly O(n) . There are several mathematical works that show that there can be no better sorting algorithm, and then O(n*log(n)) , for example, Mergesort . Since the comparator implements Mergesort , I believe that complexity should be O(n*log(n)) for better, medium, and worse.

Here you can find information about Mergesort : Mergesort

And some article on the best time complexity of the sorting algorithm: Sorting Algorithms

I could not find the exact implementation of this method, but here is a great article on how you can dig deeper into the implementation of arrays in Objective-C and look at the implementation of methods: Providing NSMutableArray

Answer 3

Sorting algorithms based on comparative costs of at least O (n log n). See Link

As its name sortedArrayUsingComparator , the method is based on comparison, so it will cost at least O (n log n).