Stable Sort in Swift

What is Stable Sorting

A stable sort is a sort that keeps the original order for any elements that compare as equal.

Considering this example.

var users = [
    User(firstName: "John", lastName: "Doe"),
    User(firstName: "Alice", lastName: "Bob"),
    User(firstName: "Sam", lastName: "Coffey"),
    User(firstName: "Ashley", lastName: "Hatch"),
    User(firstName: "Kristie", lastName: "Mewis"),
    User(firstName: "Ashley", lastName: "Sanchez")
]

let sortedUsers = users.sorted(by: { $0.firstName < $1.firstName })

We sort users by their firstName.

For a stable sort, once we find elements that compare as equal, the order of those elements before the sort will be preserved.

In this case, Ashley Hatch stays before Ashley Sanchez.

sortedUsers == [
    User(firstName: "Alice", lastName: "Bob"),
    User(firstName: "Ashley", lastName: "Hatch"),
    User(firstName: "Ashley", lastName: "Sanchez"),
    User(firstName: "John", lastName: "Doe"),
    User(firstName: "Kristie", lastName: "Mewis"),
    User(firstName: "Sam", lastName: "Coffey")
]

For an unstable sort, the order of elements with the same order doesn't guarantee to be preserved.

So there is a possibility that Ashley Hatch will come after Ashley Sanchez.

sortedUsers == [
    User(firstName: "Alice", lastName: "Bob"),
    User(firstName: "Ashley", lastName: "Sanchez"),
    User(firstName: "Ashley", lastName: "Hatch"),
    User(firstName: "John", lastName: "Doe"),
    User(firstName: "Kristie", lastName: "Mewis"),
    User(firstName: "Sam", lastName: "Coffey")
]

You can easily support sarunw.com by checking out this sponsor.

Tiny OCR: Extract text from image directly from your mac.

Try it for Free

Stable Sorting in Swift

The Swift sort has long been stable, but the documentation didn't align with the fact.

The documentation mentioned that the sorting algorithm is not guaranteed to be stable.

In Swift 5.8, the document finally update to reflect the real implementation.