Skip to content
Tutorials Center
My learning

Topics

Lesson 104 of 146 ยท Standard Library and Foundation

Sort Details

Go beyond sort() in Swift: stability, comparator rules, multi-key sorts, KeyPathComparator, SortComparator, string ordering and the cost of expensive sort keys.

You have already used sorted() and sorted(by:) in Array algorithms. Most of the time that is all you need. This lesson is about the details that decide whether a sort is correct (what a comparator must promise, why <= is a bug, why Double.nan ruins everything), whether it is predictable (stability, ties, multi-key ordering), and whether it is fast (how many comparisons happen, and how to avoid sorting by an expensive computation over and over).

We also meet the declarative tools that Foundation adds: KeyPathComparator and the SortComparator protocol, which let you say "sort by age, then by name" without writing a closure. Every number in the outputs below comes from the Swift 6.3 toolchain on this site.

What a comparator means

sorted(by:) takes a closure (Element, Element) -> Bool. Read it as the question "should the first argument come before the second?" Returning true means "yes, put a before b". The standard library calls it many times and builds the order from the answers. For that to work, the closure must describe a strict weak ordering:

  • Irreflexive: areInIncreasingOrder(a, a) is always false. An element is never "before" itself.
  • Asymmetric: if it is true for (a, b), it is false for (b, a).
  • Transitive: if a is before b, and b is before c, then a is before c.
  • Transitive equivalence: if neither of a, b comes before the other, they are "equal", and equality works consistently across the other elements.

< on integers obeys all four. A comparator that does not obey them is a bug that the compiler cannot see. The standard library documents the result as unspecified: you may get a wrongly sorted array, or on some inputs even a crash. Two classic ways to break the rules follow.

Never use <=

sorted(by: <=) looks harmless and it appears to work on small inputs, but a <= a is true, which breaks irreflexivity: the sort is told that equal elements are in strictly increasing order. Use < and, when you want to break ties, say how explicitly. If you want a descending order, use >, not >=.

NaN has no place in the order

Floating-point nan is not less than, greater than or equal to anything, not even itself. It breaks transitivity:

Swift A NaN in the middle of a sort

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

The first two lines come out as [1.5, nan, 0.5]: the array is not sorted, and nothing warns you. Filtering the NaNs first gives [0.5, 1.5]. The last line prints [0.5, 1.5, nan]: its custom comparator is a valid strict weak ordering because it places every NaN after all real numbers and compares ordinary numbers normally. If your data can contain nan, decide where it goes and encode that decision.

Stability

A sort is stable if elements that compare as equal keep their original relative order. Swift's sort and sorted are stable in every current release (the algorithm is a modified Timsort), and the current documentation promises it. That is a very useful property. Look at five people, sorted by age only:

Swift Stable sorting keeps the original order of ties

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

The output is ["Amy", "Cat", "Zed", "Bob", "Dan"] for ages (the city sort in the second line gives ["Zed", "Cat", "Dan", "Amy", "Bob"]). The two 25-year-olds appear as Amy, Cat, the same order as in the input, and the three 30-year-olds appear as Zed, Bob, Dan, also in input order. Stability is what makes the third line work: sorting by city first and then, stably, by age yields people ordered by age, and within one age by city. This "sort by the least important key first" trick is a handy way to build a multi-key sort from simple steps. But it sorts twice; the next section does it in one pass.

Other languages differ here. Some standard sorts are unstable for speed (an unstable sort is free to reorder ties, so "sort by age" may scramble your earlier ordering). If you port code that depends on stability, check the new language's guarantee.

Multi-key sorting in one pass

Tuples compare lexicographically (first elements, then the next if equal), so comparing two tuples sorts by several keys at once:

Swift Sorting by several keys with tuples

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

The result is ["Max", "Sam", "Eve", "Ivy", "Kai"]. Reading the closure: a tuple comparison is "smaller first", so to get a descending key you swap the sides for that key only. Score is swapped ($1.score on the left), time and name are not. It is compact but easy to get wrong, which is why the next tool exists.

KeyPathComparator and SortComparator

Foundation defines a protocol SortComparator: a value with a compare(_:_:) method returning a ComparisonResult (.orderedAscending, .orderedSame, .orderedDescending) and an order (.forward or .reverse). You pass one, or an array of them, to sorted(using:) or sort(using:). The ready-made KeyPathComparator compares one property selected by a key path:

Swift KeyPathComparator and sorted(using:)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

You see ["Amy", "Cat", "Zed", "Bob", "Dan"], then ["Bob", "Dan", "Zed", "Amy", "Cat"] (age descending, name ascending as the tie-break), then ["Zed", "Cat", "Dan", "Amy", "Bob"] (by city, Oslo first, ties stable) and finally orderedDescending forward for the last line: Zed (30) compared to Amy (25) is "descending", meaning Zed would come after Amy in ascending order.

Compared with a closure, comparators are data. You can store them in a property, let a user pick the order from a menu, reverse one with order: .reverse, and combine them without writing nested ternaries. The key path must point to a Comparable property for the shortcut, or you pass your own comparator for that property (below). SwiftUI's Table and SortDescriptor use exactly this model.

Writing your own SortComparator

Any type that implements compare and carries an order works, and it can be used inside a KeyPathComparator too. Here is a comparator that sorts strings by length, with the order property respected:

Swift A custom SortComparator

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

The output is ["a", "bb", "dd", "ccc"] and ["ccc", "bb", "dd", "a"]. Notice that bb and dd keep their input order in both: they compare as .orderedSame, and the sort is stable. The last line applies the comparator to a property with KeyPathComparator(\.name, comparator: ByLength()) and prints ["Ox", "Elk", "Lions", "Eagles"].

If you do not need comparators to be stored or combined, a plain closure is shorter. Use SortComparator when the sort order is configuration: chosen by users, shared between components, or built from a list.

Ordering strings

The default < on String compares by Unicode scalar values, one character at a time. It is fast and deterministic, but it is not how people expect words to be sorted:

Swift How strings are ordered

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

The plain sort gives ["B1", "a3", "b10", "b2"]: every capital letter comes before every lowercase one, and "b10" sorts before "b2" because the character 1 is less than 2. localizedStandardCompare is the "Finder-style" order people expect (a3, B1, b2, b10): case and accents are handled gently and digit runs compare as numbers. The compare(_:options:) call with .numeric and .caseInsensitive gives the same result here and lets you pick the behaviours yourself. The plain sort of names puts Banana before apple; the .caseInsensitive comparator gives ["apple", "Banana", "cherry"]. The accented letters show the scalar order: ["E", "e", "f", "รฉ"] puts รฉ last because its scalar value is larger than f.

Use plain < for internal data such as dictionary keys or identifiers, where any consistent order is fine. Use localizedStandardCompare for anything a person reads (file names, contact lists).

How much work does a sort do?

Swift's sort runs in O(n log n) time in the worst case and uses O(n) temporary memory. It also takes advantage of existing order: already sorted or reversed input is much cheaper than random input. You can see this by counting how many times the comparator is called (random data from a fixed seed so the numbers repeat):

Swift Counting comparisons

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

For 1,000 numbers the run prints about 20,000 comparisons for random data, 999 for already sorted data (one per neighbouring pair: a single scan proves it is ordered) and about 4,000 for reversed data. The exact random figure depends on the implementation, so treat it as an order of magnitude: roughly n log n with a modest constant. The practical rule: do not sort inside a loop if you can sort once, and do not re-sort data that is nearly sorted by hand; just call sort.

Expensive sort keys

Every comparison computes the key for both sides, so if the key is expensive to compute (parsing a date, normalising a string, a database lookup), sorting by it recomputes it O(n log n) times. The remedy is the decorate, sort, undecorate pattern: compute each key once, sort the pairs, throw the keys away:

Swift Compute each sort key once

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

With only four words the direct sort computes 8 keys and the decorated version computes 4 (exactly one per element). With 100,000 elements the first grows with n log n, the second stays at n. The helper function is there because Swift 6 does not allow a nonisolated function (score) to change a top-level variable.

Other tools worth knowing

  • max(by:) and min(by:) find one extreme in O(n), which is cheaper than sorting to take the first element.
  • partition(by:) reorders an array so elements for which the predicate is false come first, and returns the index where the other group starts. It is not stable and does not sort either half.
  • lexicographicallyPrecedes(_:) compares sequences element by element, like a dictionary order for arrays.
  • Sorting a dictionary produces an array, because dictionaries have no order: dictionary.sorted { $0.value > $1.value } gives [(key: String, value: Int)].
Swift partition, lexicographic order and sorted dictionaries

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

partition leaves [2, 3, 1, 8, 9, 5] with boundary 3: the first three are not greater than 4, the rest are. The order inside each side is whatever the algorithm left, which shows why partitioning is not sorting. The lexicographic sort gives [[1, 2], [1, 5], [2, 1]], and the dictionary sorted by value is [(key: "c", value: 3), (key: "b", value: 2), (key: "a", value: 1)].

Habits of reliable sorting

  • Compare with < (or >), never <=.
  • Keep floating-point NaN out of sorts, or give it an explicit place.
  • Use stability on purpose, and write tie-breaks out explicitly when the code might be ported to a language with an unstable sort.
  • Use localizedStandardCompare for text users see.
  • Sort once, at the end, rather than after every insertion.
  • Compute expensive keys once with decorate-sort-undecorate.
  • Prefer min/max(by:) when you need only the extreme.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What question does the closure of sorted(by:) answer?

    The closure returns true when its first argument should come before its second. It must describe a strict weak ordering, so equal elements give false in both directions.
  2. 2. Why is sorted(by: <=) incorrect?

    A comparator must be irreflexive. Using <= tells the sort that equal elements are in strictly increasing order, so the results are unspecified.
  3. 3. Three people have age 30 and appear in the input as Zed, Bob, Dan. After a stable sort by age they appear as:

    A stable sort keeps the original relative order of elements that compare equal. Swift's sort is stable.
  4. 4. What does people.sorted(using: [KeyPathComparator(\.age, order: .reverse), KeyPathComparator(\.name)]) do?

    Comparators are tried in order; the next one only decides ties left by the previous. Here age is descending and name breaks ties.
  5. 5. Which is the best way to avoid recomputing an expensive sort key on every comparison?

    Decorate-sort-undecorate computes n keys instead of roughly n log n, which matters when computing a key is costly.

Summary

  • A comparator answers "does the first come before the second?" and must be a strict weak ordering: use <, never <=, and keep nan out.
  • Swift's sort is stable, O(n log n), and cheap on already ordered data.
  • Tuples compare lexicographically, which gives compact multi-key sorts; swap the sides for descending keys.
  • KeyPathComparator, SortComparator and sorted(using:) express multi-key orders as data; ties fall through to the next comparator.
  • Plain string comparison uses Unicode scalar order; use localizedStandardCompare for human-facing text.
  • For expensive keys, compute once and sort pairs; for one extreme value, use min(by:)/max(by:).
  • partition(by:) splits without sorting and is not stable.

Next: Key Paths