2

I need to sort an array that holds numeric elements. However, I'm not sure if it would be efficient to use the sort method since I don't know time complexity of this method. Apple document doesn't mention it either. So I would like to know what the time complexity of this method is and what kind of sorting algorithm it uses.

Improve this question
0

1 Answer 1

Reset to default
3

Swift uses Introsort. Looking at the source code we see that the chosen pivot is the first element.

link to wikipedia: https://en.wikipedia.org/wiki/Introsort

from the wikipedia page:

(...), one of the critical operations is choosing the pivot: the element around which the list is partitioned. The simplest pivot selection algorithm is to take the first or the last element of the list as the pivot, causing poor behavior for the case of sorted or nearly sorted input.

Looking at that wikipedia page, it is entirely predictable, given the implementation choice, that Swift's sorting performance is worst for sorted inputs. Its average performance‎ is ‎O(n log n) which happens to also be its worst case.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Thanks for the links and through explanation

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.