A quick pitch to add a guarantee that the stdlib's sort is stable! This has been true for a long time, so we should promise that it will stay that way.

## Introduction

Swift's sorting algorithm was changed to be stable before Swift 5, but we've never updated the documentation to provide that guarantee. Let's commit to the sorting algorithm being stable so that people can rely on that behavior.

## Motivation

A *stable sort* is a sort that keeps the original relative order for any elements that compare as equal or unordered. For example, given this list of players that are already sorted by last name, a sort by first name preserves the original order of the two players named "Ashley":

```
var roster = [
Player(first: "Sam", last: "Coffey"),
Player(first: "Ashley", last: "Hatch"),
Player(first: "Kristie", last: "Mewis"),
Player(first: "Ashley", last: "Sanchez"),
Player(first: "Sophia", last: "Smith"),
]
roster.sort(by: { $0.first < $1.first })
// roster == [
// Player(first: "Ashley", last: "Hatch"),
// Player(first: "Ashley", last: "Sanchez"),
// Player(first: "Kristie", last: "Mewis"),
// Player(first: "Sam", last: "Coffey"),
// Player(first: "Sophia", last: "Smith"),
// ]
```

For users who are unaware that many sorting algorithms aren't stable, an unstable sort can be surprising. Preserving relative order is an expectation set by software like spreadsheets, where sorting by one column, and then another, is a way to complete a sort based on multiple properties.

Sort stability isn't always observable. When a collection is sorted based on the elements' `Comparable`

conformance, like sorting an array of integers, "unordered" elements are typically indistinguishable. In general, sort stability is important when elements are sorted based on a subset of their properties.

## Proposed solution

The standard library's implementation of `sort()`

and `sorted()`

has been stable since before ABI stability was declared in Swift 5, but the documentation explicitly doesn't make this guarantee:

The sorting algorithm is not guaranteed to be stable. A stable sort preserves the relative order of elements that compare as equal.

Let's change that! Since all current versions of the Swift runtime include a stable sort, this change can be made to the standard library documentation only:

```
- /// The sorting algorithm is not guaranteed to be stable. A stable sort
+ /// The sorting algorithm is guaranteed to be stable. A stable sort
/// preserves the relative order of elements that compare as equal.
```

## Source compatibility

This change codifies the existing standard library behavior, so it is compatible with all existing source code.

## Effect on ABI stability

The change to make sorting stable was implemented before ABI stability, so all ABI-stable versions of Swift already provide this behavior.

## Effect on API resilience

Making this guarantee explicit requires that any changes to the sort algorithm maintain stability.

## Alternatives considered

There are a variety of other sorting-related improvements that could be interesting to pursue, including key-path or function-based sorting, sorted collection types or protocols, sort descriptors, and more. These ideas can be explored in future pitches and proposals.