When working with arrays and other collections, it’s incredibly common to want to sort the values that they contain, especially when dealing with local user data. In certain situations, we might give our users explicit control over how various lists are sorted, while other situations might require us to automatically sort a given data set in order to make it more predictable and easier to handle.

Regardless, both Foundation and the Swift standard library ship with a number of different APIs that can be used to implement that kind of sorting logic. This week, let’s take a look at some of those APIs, and how we could also augment them in order to make more advanced sorting tasks easier to perform.

Let’s start with the basics

Any Swift Sequence (which includes common data structures, like arrays, dictionaries, and sets) can be sorted using the sorted API, which takes a closure that’s used to determine the sort order by comparing two elements at a time.

For example, here we’re sorting an array of TodoItem values based on the date of each instance, and by using the less-than operator (<) to perform our comparison, we’ll end up with an array that’s sorted in ascending order:

struct TodoItem {
    var date: Date
    ...
}

func sortItemsByDate(_ items: [TodoItem]) -> [TodoItem] {
    items.sorted { itemA, itemB in
    itemA.date < itemB.date
}
}

The built-in sorted method can be called on any Sequence (so not just arrays). However, it always returns an Array as its output, regardless of what type of collection that it was called on.

While using sorted like we do above gives us complete control over our sorting operation, what’s really nice is that any collection that contains Comparable values can be sorted without requiring us to pass any closure at all — meaning that something like an array of Int values can be sorted simply by doing this:

let numbers: [Int] = ...
let sortedNumbers = numbers.sorted()

By default, the above version of sorted will sort each element in ascending order, but if we’d rather use descending order, then we can combine the closure-based version with the fact that Swift supports passing operators as functions — which lets us do this:

let numbers: [Int] = ...
let sortedNumbers = numbers.sorted(by: >)

So the built-in sorted API (and its in-place variant, called sort) are incredibly easy to use when working with Comparable values, and since Swift has such a protocol-oriented design, making our own types conform to Comparable is often the simplest way to enable collections containing such values to be sorted.

For example, here we’re making a Tag type conform to Comparable using its underlying rawValue, which in turn lets us simply call sorted() on any collection containing Tag values:

struct Tag: RawRepresentable {
    var rawValue: String
}

extension Tag: Comparable {
    static func <(lhs: Tag, rhs: Tag) -> Bool {
        lhs.rawValue < rhs.rawValue
    }
}

let tags = loadAllTags()
let sortedTags = tags.sorted()

However, although it might be tempting to use the above approach for all types that are involved in any kind of sorting, doing so could give certain types quite odd semantics.

Take the TodoItem type that we used earlier as an example. Although we could make it conform to Comparable using its date property, that wouldn’t really make any sense outside of the realm of sorting, and what if we wanted to sort some of our TodoItem collections based on a property other than date?

Custom sorting using key paths

Of course, one way to deal with non-Comparable values would be to simply continue to use the sorted API that requires us to pass a manual closure, but if we’re performing that kind of operation in multiple places across our code base, then always having to write such closures can quickly become both repetitive and quite error prone.

So let’s also explore how we could extend the built-in suite of sorting APIs with a few conveniences that would enable us to easily sort any collection based on one of its Element type’s properties. One way to do that would be to do what we did in “The power of key paths in Swift”, and extend Sequence with an API that lets us use a KeyPath to sort a given collection — like this:

extension Sequence {
    func sorted<T: Comparable>(by keyPath: KeyPath<Element, T>) -> [Element] {
        sorted { a, b in
            a[keyPath: keyPath] < b[keyPath: keyPath]
        }
    }
}

With the above in place, we’ll now be able to use Swift’s key path literal syntax to sort our collections based on any Comparable property that our elements contain:

let sortedTags = tags.sorted(by: \.rawValue)
let sortedTodoItems = todoItems.sorted(by: \.date)

That’s definitely an improvement over our previous, closure-based approach. However, we’re currently assuming that all of our collections should be ordered in ascending order, which might not be the case.

So, to support other sort orders (including completely custom ones), let’s also add a closure parameter to our new API as well. Thanks to the power of default arguments, we can make that change in a way that doesn’t make our previous API any harder to use, since we can use the < operator as our default closure — like this:

extension Sequence {
    func sorted<T: Comparable>(
        by keyPath: KeyPath<Element, T>,
        using comparator: (T, T) -> Bool = (<)
    ) -> [Element] {
        sorted { a, b in
            comparator(a[keyPath: keyPath], b[keyPath: keyPath])
        }
    }
}

With the above in place, we’ll now be able to easily sort any collection (such as our todoItems array from before) in descending order by passing the greater-than operator as our comparator — just like we did when using the built-in sorted API:

let mostRecentTodoItems = todoItems.sorted(by: \.date, using: >)

Really nice! Next, let’s take a look at how we could keep extending the above API to also support multiple key paths, instead of just one.

Sorting on multiple properties

Let’s now say that we wanted to sort an array of articles, first based on the categories that they belong to, and then alphabetically based on their titles. One way to make that happen would be to once again go back to the closure-based version of sorted, and implement something like this:

func sortArticlesByCategory(_ articles: [Article]) -> [Article] {
    articles.sorted { articleA, articleB in
        guard articleA.category == articleB.category else {
            return articleA.category < articleB.category
        }

        return articleA.title < articleB.title
    }
}

Just like the other examples that we’ve taken a look at so far, if the above method is the only place in which we need to sort a collection based on multiple properties, then there’s no need to change things whatsoever. However, if that’s a pattern that we’re repeating in multiple places, then it might warrant another abstraction.

This time, let’s take some inspiration from Swift’s predecessor, Objective-C, which ships with a type called NSSortDescriptor that can be used to describe exactly how we want a given collection to be sorted. Although that type can also be used in Swift, it can only be used with Objective-C collections, such as NSArray — which in turn would require us to sacrifice the strong type safety that Swift’s own collections give us.

Thankfully, creating a “Swift-native” version of it doesn’t have to be that complicated. Let’s start with a struct called SortDescriptor, which is really just a wrapper around a closure that compares two values and returns a ComparisonResult (which is another Objective-C type that we will use directly):

struct SortDescriptor<Value> {
    var comparator: (Value, Value) -> ComparisonResult
}

Then, since we’re still primarily looking to sort our various collections based on key paths, let’s extend our new SortDescriptor type with a static method that’ll let us easily create an instance using a given KeyPath:

extension SortDescriptor {
    static func keyPath<T: Comparable>(_ keyPath: KeyPath<Value, T>) -> Self {
        Self { rootA, rootB in
            let valueA = rootA[keyPath: keyPath]
            let valueB = rootB[keyPath: keyPath]

            guard valueA != valueB else {
                return .orderedSame
            }

            return valueA < valueB ? .orderedAscending : .orderedDescending
        }
    }
}

Since we’re now using ComparisonResult, rather than plain Bool values, we’re going to need a new way to describe our desired sort order. One way to do that would be to introduce a simple enum that describes each order that we’re looking to support, for example like this:

enum SortOrder {
    case ascending
    case descending
}

With the above pieces in place, let’s now go ahead and implement our actual sorting algorithm — which will use an array of SortDescriptor values, along with a given SortOrder, to form a closure that we can then pass to the standard library’s sorted method:

extension Sequence {
    func sorted(using descriptors: [SortDescriptor<Element>],
                order: SortOrder) -> [Element] {
        sorted { valueA, valueB in
            for descriptor in descriptors {
                let result = descriptor.comparator(valueA, valueB)

                switch result {
                case .orderedSame:
                    // Keep iterating if the two elements are equal,
                    // since that'll let the next descriptor determine
                    // the sort order:
                    break
                case .orderedAscending:
                    return order == .ascending
                case .orderedDescending:
                    return order == .descending
                }
            }

            // If no descriptor was able to determine the sort
            // order, we'll default to false (similar to when
            // using the '<' operator with the built-in API):
            return false
        }
    }
}

While the above new method will already give us a very nice and easy way to sort a collection based on multiple Element properties, if we’re primarily going to use ascending as our SortOrder, then we could also add the following convenience API — which will let us pass a list of SortDescriptor values using variadic parameter syntax:

extension Sequence {
    func sorted(using descriptors: SortDescriptor<Element>...) -> [Element] {
        sorted(using: descriptors, order: .ascending)
    }
}

Yes, the above is a convenience API on top of another convenience API. Full-stack convenience, if you will.

With that, our new multi-property sorting API is now complete, so let’s take it for a spin. Here’s how we could now easily sort our Article array from before, by simply passing a list of the key paths that we want to sort it by:

func sortArticlesByCategory(_ articles: [Article]) -> [Article] {
    articles.sorted(using: .keyPath(\.category), .keyPath(\.title))
}

Also, since we didn’t hard-code our SortDescriptor type to always use key paths — we can now use it as a powerful, general-purpose sorting API, even when we’d like to use a list of highly custom sorting algorithms.

In-place sorting and performance

So far, the examples that we’ve taken a look at have all used the system-provided sorted API under the hood, but depending on each use case and the kind of performance characteristics that we’re going for, using the in-place variant of that API might actually be a better option.

To illustrate, let’s now say that we’re working on a game that includes the following ScoreList type, which ensures that an underlying array of Int-based scores remains sorted, even as new scores are added to it:

struct ScoreList {
    private(set) var scores: [Int]

    init(scores: [Int]) {
        self.scores = scores.sorted()
    }

    mutating func addScore(_ score: Int) {
        scores.append(score)
        scores = scores.sorted()
    }
}

Now, let’s compare the above to the following implementation, which uses the sort method to sort our scores array in place, rather than creating a copy of it:

struct ScoreList {
    ...

    mutating func addScore(_ score: Int) {
        scores.append(score)
        scores.sort()
    }
}

When running in DEBUG mode, the above two implementations have almost identical performance characteristics — which is to be expected since both sort and sorted have a time complexity of O(n log n). However, if we instead run our app in RELEASE mode (which should always be used when comparing performance), then something interesting happens.

Not only are both of our implementations about 100 times faster in RELEASE mode (yes, no kidding!), but our in-place, sort-based version is now almost twice as fast compared to the sorted-based approach. That’s because, during release builds, the compiler performs many kinds of optimizations when it comes to collections and value types, which in this case works remarkably well — especially when our collection is mutated in place.

Conclusion

Swift’s built-in sorting functionality is a great example of how the standard library exposes several advanced, high-performance algorithms as a really simple suite of APIs, especially when working with Comparable values.

Although those built-in APIs are likely going to be more than enough for many apps, sometimes we might want to augment them by adding a few conveniences — for example in order to support simple, property-based sorting. I hope that you found the examples of doing that interesting, and if you have any questions, comments or feedback, then feel free to reach out via either Twitter or email.

Thanks for reading! 🚀