Swift Sorting Algorithm

      No Comments on Swift Sorting Algorithm

Now that swift is open source we can actually check from the source code which algorithm is actually used by swift array.Early this year Dejan wrote an amazing article about sorting algorithms. In this article he was comparing common sorting algorithms with the swift sorting algorithm. What we could observe from his conclusion is that swift sorting algorithm is a lot faster than any other concurrent. Now that swift is open source we can actually check from the source code which algorithm is actually used by swift array.

Why should I do that?

Usually in our apps we don’t really have arrays that are that big to require special attentions in terms of sorting. Still I truly believe that knowing what’s under the hood can help to understand which is the real complexity of the algorithms that we are going to write. This will help us to make wise decisions to optimise critical parts of our code. To invest time in optimisation is, in my opinion, never a waste of time if you have an eye for the future.

Example: Let’s suppose that we have a list of objects coming from our networking layer already sorted, the user edits one element, and we must re-sort the array. Is it efficient to do it using swift sort?

Another reason is that I saw too many times the use of sorted()  also on the main thread like it was the access to a variable. The fact that is not code that we directly own, often let us forget that there is a lot of computation behind that sorted() .

Which is the ideal sorting algorithm?

Unfortunately the perfect sorting algorithm does not exist. Each known sorting algorithm might have a practical application based on the situation you find in your app. In the previous example where we had a list already sorted, subsequent sorting should be performed using insertion sort, because it is extremely efficient with lists that are already sorted.

Still there is a list of requirements that a sorting algorithm must check to be considered perfect:

  • It must be stable: Equals elements must maintain the same order.
  • It must be in-place: uses O(1) extra space.
  • Its worst case must be with complexity O( n log(n) )
  • It must be adaptive: which means that on collections that are already sorted the time complexity must tend to O(n)

IntroSort

IntroSort is the algorithm used by swift to sort a collection. Introsort is an hybrid algorithm invented by David Musser  in 1993 with the purpose of giving a generic sorting algorithm for the C++ standard library. The classic implementation of introsort expect a recursive Quicksort with fallback to Heapsort in case the recursion depth level reached a certain max. The maximum depends on the number of elements in the collection and it is usually 2 * log(n). The reason behind this “fallback” is that if Quicksort was not able to get the solution after 2 * log(n) recursions, probably it hit its worst case and it is degrading to complexity O( n2 ). To optimise even further this algorithm, for swift implementation there is an extra step in each recursion where the partition is sorted using InsertionSort if the count of the partition is less than 20.

The number 20 is an empiric number obtained observing the behaviour of InsertionSort with lists of this size. Basically it is statistically probable that InsertionSort tends to O(n) with small collections.

In pseudocode swift introSort would look like this:

Comparison

I prepared an open source command line project to compare the performances of introsort with other well known sorting algorithms. This project generates three arrays of 100.000 random UInt64. These three arrays are identical. The difference is in the way we store the numbers.

  • The first is a bare [UInt64] array.
  • The second is an array of MyUInt64 which is a struct that contains the variable value that is UInt64. This array was created to observe the behaviour of Array with Elements not conforming to Comparable
  • The third is an array of MyUInt64Object which is an NSObject containing the variable value that is UInt64. This array has the purpose to observe the behaviour of Array with Elements that are NSObjects.

The results are quite interesting. Running the project we observe immediately a big difference between the use of sorted()  against sorted(by: )

🔸 Swift sort:  1,9 * 10 -2 ± 0,2 * 10 -2

🔶 No predicate:  7,2 * 10 -3 ± 0,6 * 10 -3  | 2.7 times faster than swift sort with a predicate

Without an explicit predicate, the same swift algorithm is almost 3 times faster than the version that has the closure to estimate the order of the elements in the array.

If we look in the source code on the swift GitHub project we can see that the implementation is a template. Basically the code for sorted()  is duplicated for the sorted(by: )  implementation with the difference that in the second case the comparison is made through the closure passed in the by parameter, while the first version simply compare the two elements using the < operator.

I was very surprised when I saw this discrepancy the first time because this means that the access to the closure slows down the sorting performance significantly.

 

Another important difference we found was comparing the result of the array of MyUInt64Object against the other two. Sorting an array of NSObjects is consistently slower than the same sorting algorithm used on a collection of Structs.

This wasn’t too surprising, and it happens because Array fallback on NSArray when the Elements are NSObjects.

These are the results of my research:

 100k items Comparable Not Comparable NSObjects Already sorted
sorted() 0,007 0,002
sorted(by: <) 0,019 0,019 0,110 0,018
introSorted(by: <) 0,020 0,019 0,130 0,019
quickSorted(by: <) 0,012 0,013 0,051 0,004
heapSorted(by: <) 0,033 0,035 0,260 0,036
mergeSorted(by: <) 0,110 0,110 0,300 0,096
insertionSorted(by: <) 2,600 2,600 0,0002

Please note: Mergesort is consistently slower than its in-place concurrents. The reason is that it does not exist a truly efficient in-place implementation of this algorithm. Our merge sort implementation relies on arrays, and swift Array data structure is not the ideal c array data structure.

  • Accessing any value at a particular index in an array is at worst O(log n), but should usually be O(1)
  • Inserting or deleting an object is at worst O(n log(n) ) but will often be O(1).

I hope that this research will help you to find the best way to optimise your code when it comes of keeping things in order.

1+

Leave a Reply