How does sorting work in Swift, and what do you need to watch out for?

2.1.8 · L2 · Interview

Predict first

What does this print?

var a = [3, 1, 2]
let b = a.sort()
print(b)
  • [1, 2, 3]
  • ()

Predict first

What does this print?

print([3, 1, 2].sorted(by: >))
  • [1, 2, 3]
  • [3, 2, 1]

Mental model. Sorting is lining people up by height. The rule must say clearly who stands first; “taller or equal” leaves two people each told to go before the other.

sort() sorts in place and returns nothing; sorted() returns a new array. Both are O(n log n) and take an areInIncreasingOrder closure that must be a strict weak ordering: use <, never <=. A comparator that says two equal items are each “less than” the other breaks the algorithm’s assumptions, with unpredictable results.

Do not depend on equal elements keeping their relative order unless your toolchain’s documentation guarantees it. Sort by a total key instead, adding a tiebreaker such as an id. There is no binary search in the standard library; firstIndex(where:) and contains are linear scans.

sort() is the in-place version and returns Void. Use sorted() if you want a new array.

Passing > as the comparator sorts descending. It is a valid strict weak ordering.

Common traps

  • Comparing with <=. It violates strict weak ordering and can misbehave or crash.
  • Assigning the result of sort(). It returns Void, so you sorted in place and captured ().

They might follow up with

  • How do you sort by two keys? Compare tuples: sorted { ($0.last, $0.first) < ($1.last, $1.first) }.
  • How do you search a sorted array fast? Write a binary search, or use partitioningIndex(where:) from swift-algorithms.

Related questions

  • 2.1.7 map, filter, compactMap, flatMap, reduce, forEach: when do you use each, and what bites?
  • 2.1.3 When is the standard library not enough, and what does swift-collections add?

← map, filter, compactMap, flatMap, reduce, forEach: when do you use…   Sequence, Collection, BidirectionalCollection… →