An extensive guide to sorting Arrays in Swift

When you're working with Arrays in Swift, it's likely that you'll want to sort them at some point. In Swift, there are two ways to sort an Array:

1. Through the Comparable implementation for each element in your array
2. By providing a closure to perform a manual/specialized comparison between elements

If you have a homogenous array of elements, for example [String], you can rely on String's implementation of Comparable to sort an array of String in some sensible manner. There are two ways to sort an array of Comparable elements:

var strings = ["Oh", "Hello", "World", "This", "Is", "An", "Unsorted", "Array"]

// sort in-place
strings.sort()

// create a new array with sorted elements
let sorted = strings.sorted()

If you're not familiar with the Comparable protocol in Swift, take a look at the documentation for this protocol. In short, objects that are Comparable can be compared using < to determine order and with == to determine equality. If two elements are equal according to == then comparing them with < is expected to be false. This means that you can sort an array through the Comparable protocol because that provides all the tools to determine order.

The output from the code sample above is the following:

["An", "Array", "Hello", "Is", "Oh", "This", "Unsorted", "World"]

Based on this output, you can derive that String's default Comparable implementation sorts elements in increasing alphabetical order.

Whenever Swift's default sorting algorithm encounters an element that is equal to another element, it will preserve the original order of these elements in the output. In other words, Swift's sorting algorithm is a so-called stable sorting algorithm. If you want to learn more about how Swift's sort() is implemented, it uses an algorithm called IntroSort and you can learn more about it in this Swift Algorithms Club article.

If the default sorting behaviour for String isn't the behavior you're looking for, or you want to sort an array of items that aren't Comparable, you can use the sort(by:) and sorted(by:) sorting methods to take control of how your array is sorted. The difference between sort(by:) and sorted(by:) is the same as the difference between sort() and sorted(); the former sorts the array in-place, the latter returns a new array.

Here's an example of how sorted(by:) can be used to sort an array of strings by their length in descending order:

let sortedByLength = strings.sorted(by: { lhs, rhs in
  return lhs.count > rhs.count
})

The closure that's passed to sorted(by:) is called as often as needed with two elements to determine their order and you are expeced to return true if the first element (lhs) should precede the second element (rhs) is in the final result.

Because this sorting method is defined as O(n log n) you should be cautious about the amount of work you do in your closure. Doing too much work will result in a very slow sort and you shouldn't want that. This also applies to the regular sort() implementation, so if you're implementing your own Comparable conformance to make sorting an array of your own structs more straightforward, make sure your implementation is as efficient as possible.

Tip: If you're not familiar with Big-O notation, take a look at this post to learn more.

I mentioned earlier that if Swift's sorting algorithm encounters two equal elements, this also applies when you use sorted(by:) even though you can't express equality (you either return true or false). Swift's sorting algorithm processes your array in-order so it knows that if you return false from your sorting closure, an element should not precede the element that it's being compared to. If they're equal, any subsequent comparisons between both elements will return the same value, which means that these two elements will not relative positions unless they're not equal.

For example, sorting our original array while printing all performed comparisons yields this result:

Hello > Oh: true
World > Oh: true
World > Hello: false
This > Oh: true
This > World: false
Is > Oh: false
An > Is: false
Unsorted > An: true
Unsorted > Is: true
Unsorted > Oh: true
Unsorted > This: true
Unsorted > World: true
Unsorted > Hello: true
Array > An: true
Array > Is: true
Array > Oh: true
Array > This: true
Array > World: false

This output gives us a lot of insight into what happens. First Oh and Hello are compared and I return true. This means that Hello should precede Oh. This puts Hello at the first position in the sorted array and Oh is at the second position. Next, the third item in the array (World) is compared to the second (Oh). I return true Because World should precede Oh. Next, the algorithm wants to know whether World should precede Hello. They're equal in length so I return false ("Hello".count > "World".count is false).

The next interesting lines are:

Unsorted > World: true
Unsorted > Hello: true

The word Unsorted is longer than both World and Hello so it preceded both words. However, placing Unsorted before Hello does not change the order in which Hello and World appear in the final result.

The last comparison in our output is Array > World. This comparison returns false because these words are of equal length. And because Array occurs after World in the original, that order is maintained; we stop moving Array upward in the final result as soon as we return false.

While this experiment was useful to provide you with a basic understanding of how Swift's sorting works at the time of writing, you shouldn't rely on the details too much. Your main takeways should be:

• Swift's sorting is stable; this means that equal elements keep their relative order
• Swift's sorting is O(n log n) at worst

And of course the most important takeaway by far is that you can sort an array of Comparable elements with sort() and sorted(). If you need more control over how your elements are sorted, or if they aren't Comparable you can use sort(by:) or sorted(by:).

If you have any questions about this tip, or if you have feedback for me, make sure to reach out on Twitter.