# Most Played, Then A to Z: Stable and Built-In Sorts

List songs by artist, then by title, with your language's built-in sort, and keep songs that tie in the order the user chose: why sorting twice scrambles them in C#, and the promise a sort has to make to keep that order, stability.

Journeyman · Data Structures · Updated November 17, 2026

By Gregor Dzierzon

## After this lesson you can

- Sort by more than one key with your language's built-in sort
- Explain what a stable sort is and when it matters

## Key takeaways

- Every language's built-in sort is O(n log n). In real code, use it rather than writing your own.
- You tell the built-in sort what to sort by: a key (the plays, the artist) or a comparison of two items.
- Sort by more than one key by comparing the first key, and only when it ties, the next.
- A stable sort keeps items that tie in the order they were in. Java's object sort, Python's sort, JavaScript's sort and C#'s OrderBy are stable; C#'s List.Sort is not.
- Sorting twice, by title and then by artist, keeps each artist's songs in title order only with a stable sort; otherwise sort by both keys at once.

**Before this:** *Can Any Sort Go Faster? The n log n Speed Limit* (you've written four sorts by hand, and the fast ones are as fast as comparing gets).

In real code you'll write none of those four sorts: every language has a built-in sort that's faster than anything you'd write in an afternoon and has been tested by millions of programs. But here's a bug report from a music app that uses it.

The library screen has a column header for each field. A user clicks **Title**, then **Artist**, expecting every artist's songs in title order. In the C# version of the app, each artist's songs come back scrambled, and after a refresh they're scrambled differently. In the Java and Python versions, the same two clicks work.

## What would you try?

**Write your own sort.** Your merge sort from *A Million Songs to Sort Before Bedtime: Merge Sort* gets it right, as you'll see. But now the app carries its own sort, tested only by you, in place of one used by millions.

**Sort twice, again.** Click Title, then Artist, and sort by title and then by artist in code: that's what the app already does. The second sort is the one that scrambles the songs.

**One combined key, artist then title.** It fixes these two columns. But the screen sorts by whichever columns the user clicked, in whatever order, and the app would have to remember every click and build the key from them.

**Add each song's place in the list as the last tie-breaker.** Sort by artist, and when two artists tie, by where the songs were before this sort. That works, every time, but it's work you'd do by hand on every sort.

## The questions that lead to it

**What did the first sort know that the second threw away?** The title order. After clicking Title, each artist's songs were already in title order; the second sort only had to leave them that way.

**What would a sort have to promise to keep it?** That two items it can't tell apart, two songs by the same artist, come out in the order they went in. Java's and Python's built-in sorts make that promise. C#'s `List<T>.Sort` doesn't.

## How it got its name

That promise was so useful that it got a name: a sort that keeps tied items in their original order is a **stable sort**. A sort that may shuffle them is **unstable**. With a stable sort, two clicks give two keys, one sort at a time, and the ties keep whatever order the last click gave them.

![The same six songs, first listed A to Z by title, then sorted by plays, most first, two ways: a stable sort, where the songs that tie keep their A to Z title order, Blue Hour before Copper Moon and Amber Road, Desert Lights, Falling Up; and an unstable sort, which can give the tied songs back in another order, such as Copper Moon before Blue Hour](https://fsdtrainingmedia.blob.core.windows.net/public/images/2026/11/d4fea883f47f4d53b2e83002aca34b8d.webp)

C#'s `List<T>.Sort` and `Array.Sort` are unstable: on a list of up to 16 items they happen to keep ties in order, and on a longer one they can scramble them, which is why the bug hides in small tests. C#'s LINQ `OrderBy` and `ThenBy` are stable. Here's which is which in every language, and what's inside.

## What's inside your language's sort

All of them are O(n log n), and all of them mix the sorts from this module:

| Language | The built-in sort | What's inside | Stable? |
|---|---|---|---|
| C# | `List<T>.Sort`, `Array.Sort` | introsort: quicksort, switching to heapsort if it goes too deep, and insertion sort for short stretches | no |
| C# | LINQ `OrderBy`, `ThenBy` | a stable sort | yes |
| Java | `List.sort`, `Collections.sort`, `Arrays.sort` on objects | Timsort: merge sort plus insertion sort | yes |
| Java | `Arrays.sort` on `int[]` and other plain numbers | dual-pivot quicksort | no (two equal numbers can't be told apart anyway) |
| Python | `sorted`, `list.sort` | Timsort (since Python 3.11 it picks which stretches to merge with a newer rule, Powersort) | yes |
| JavaScript, TypeScript | `Array.prototype.sort`, `toSorted` | Timsort in Node.js and Chrome | yes |

Timsort looks for stretches of the list that are already in order and merges them, so it's especially fast on data that's almost sorted, the same talent you saw in insertion sort.

## Sort by a key, then by two

A **sort key** is the thing you sort by: a song's plays, its artist, its title. Here are six songs from a music library, listed A to Z by title, sorted two ways: by plays, most first, and then by artist, with songs by the same artist in title order:

```csharp
List<Song> songs = new List<Song>
{
    new Song("Amber Road", "Marigold Avenue", 120),
    new Song("Blue Hour", "Night Bus Trio", 340),
    new Song("Copper Moon", "Marigold Avenue", 340),
    new Song("Desert Lights", "Night Bus Trio", 120),
    new Song("Echo Park", "Copper Kettle Band", 510),
    new Song("Falling Up", "Copper Kettle Band", 120)
};

Console.WriteLine("By plays, most first:");
foreach (Song song in songs.OrderByDescending(song => song.Plays))
{
    Console.WriteLine(song.Plays + " plays: " + song.Title);
}

Console.WriteLine("By artist, then title:");
foreach (Song song in songs.OrderBy(song => song.Artist, StringComparer.Ordinal).ThenBy(song => song.Title, StringComparer.Ordinal))
{
    Console.WriteLine(song.Artist + ": " + song.Title);
}

record Song(string Title, string Artist, int Plays);
```

```text
By plays, most first:
510 plays: Echo Park
340 plays: Blue Hour
340 plays: Copper Moon
120 plays: Amber Road
120 plays: Desert Lights
120 plays: Falling Up
By artist, then title:
Copper Kettle Band: Echo Park
Copper Kettle Band: Falling Up
Marigold Avenue: Amber Road
Marigold Avenue: Copper Moon
Night Bus Trio: Blue Hour
Night Bus Trio: Desert Lights
```

```java
record Song(String title, String artist, int plays) {
}

void main() {
    List<Song> songs = List.of(
        new Song("Amber Road", "Marigold Avenue", 120),
        new Song("Blue Hour", "Night Bus Trio", 340),
        new Song("Copper Moon", "Marigold Avenue", 340),
        new Song("Desert Lights", "Night Bus Trio", 120),
        new Song("Echo Park", "Copper Kettle Band", 510),
        new Song("Falling Up", "Copper Kettle Band", 120));

    List<Song> byPlays = new ArrayList<>(songs);
    byPlays.sort(Comparator.comparingInt(Song::plays).reversed());
    IO.println("By plays, most first:");
    for (Song song : byPlays) {
        IO.println(song.plays() + " plays: " + song.title());
    }

    List<Song> byArtist = new ArrayList<>(songs);
    byArtist.sort(Comparator.comparing(Song::artist).thenComparing(Song::title));
    IO.println("By artist, then title:");
    for (Song song : byArtist) {
        IO.println(song.artist() + ": " + song.title());
    }
}
```

```text
By plays, most first:
510 plays: Echo Park
340 plays: Blue Hour
340 plays: Copper Moon
120 plays: Amber Road
120 plays: Desert Lights
120 plays: Falling Up
By artist, then title:
Copper Kettle Band: Echo Park
Copper Kettle Band: Falling Up
Marigold Avenue: Amber Road
Marigold Avenue: Copper Moon
Night Bus Trio: Blue Hour
Night Bus Trio: Desert Lights
```

```python
from dataclasses import dataclass


@dataclass
class Song:
    title: str
    artist: str
    plays: int


songs = [
    Song("Amber Road", "Marigold Avenue", 120),
    Song("Blue Hour", "Night Bus Trio", 340),
    Song("Copper Moon", "Marigold Avenue", 340),
    Song("Desert Lights", "Night Bus Trio", 120),
    Song("Echo Park", "Copper Kettle Band", 510),
    Song("Falling Up", "Copper Kettle Band", 120),
]

print("By plays, most first:")
for song in sorted(songs, key=lambda song: song.plays, reverse=True):
    print(f"{song.plays} plays: {song.title}")

print("By artist, then title:")
for song in sorted(songs, key=lambda song: (song.artist, song.title)):
    print(f"{song.artist}: {song.title}")
```

```text
By plays, most first:
510 plays: Echo Park
340 plays: Blue Hour
340 plays: Copper Moon
120 plays: Amber Road
120 plays: Desert Lights
120 plays: Falling Up
By artist, then title:
Copper Kettle Band: Echo Park
Copper Kettle Band: Falling Up
Marigold Avenue: Amber Road
Marigold Avenue: Copper Moon
Night Bus Trio: Blue Hour
Night Bus Trio: Desert Lights
```

```javascript
const songs = [
  { title: "Amber Road", artist: "Marigold Avenue", plays: 120 },
  { title: "Blue Hour", artist: "Night Bus Trio", plays: 340 },
  { title: "Copper Moon", artist: "Marigold Avenue", plays: 340 },
  { title: "Desert Lights", artist: "Night Bus Trio", plays: 120 },
  { title: "Echo Park", artist: "Copper Kettle Band", plays: 510 },
  { title: "Falling Up", artist: "Copper Kettle Band", plays: 120 },
];

console.log("By plays, most first:");
for (const song of [...songs].sort((a, b) => b.plays - a.plays)) {
  console.log(`${song.plays} plays: ${song.title}`);
}

console.log("By artist, then title:");
for (const song of [...songs].sort((a, b) => a.artist.localeCompare(b.artist) || a.title.localeCompare(b.title))) {
  console.log(`${song.artist}: ${song.title}`);
}
```

```text
By plays, most first:
510 plays: Echo Park
340 plays: Blue Hour
340 plays: Copper Moon
120 plays: Amber Road
120 plays: Desert Lights
120 plays: Falling Up
By artist, then title:
Copper Kettle Band: Echo Park
Copper Kettle Band: Falling Up
Marigold Avenue: Amber Road
Marigold Avenue: Copper Moon
Night Bus Trio: Blue Hour
Night Bus Trio: Desert Lights
```

```typescript
type Song = { title: string; artist: string; plays: number };

const songs: Song[] = [
  { title: "Amber Road", artist: "Marigold Avenue", plays: 120 },
  { title: "Blue Hour", artist: "Night Bus Trio", plays: 340 },
  { title: "Copper Moon", artist: "Marigold Avenue", plays: 340 },
  { title: "Desert Lights", artist: "Night Bus Trio", plays: 120 },
  { title: "Echo Park", artist: "Copper Kettle Band", plays: 510 },
  { title: "Falling Up", artist: "Copper Kettle Band", plays: 120 },
];

console.log("By plays, most first:");
for (const song of [...songs].sort((a, b) => b.plays - a.plays)) {
  console.log(`${song.plays} plays: ${song.title}`);
}

console.log("By artist, then title:");
for (const song of [...songs].sort((a, b) => a.artist.localeCompare(b.artist) || a.title.localeCompare(b.title))) {
  console.log(`${song.artist}: ${song.title}`);
}
```

```text
By plays, most first:
510 plays: Echo Park
340 plays: Blue Hour
340 plays: Copper Moon
120 plays: Amber Road
120 plays: Desert Lights
120 plays: Falling Up
By artist, then title:
Copper Kettle Band: Echo Park
Copper Kettle Band: Falling Up
Marigold Avenue: Amber Road
Marigold Avenue: Copper Moon
Night Bus Trio: Blue Hour
Night Bus Trio: Desert Lights
```

There are two ways to say what to sort by, and the languages lean on different ones:

- **A key:** a small function that picks the sort key out of each item. C#'s `OrderBy(song => song.Plays)`, Java's `Comparator.comparingInt(Song::plays)` and Python's `key=lambda song: song.plays` all do this. For more than one key, C# adds `ThenBy`, Java `thenComparing`, and Python gives back a tuple, `(song.artist, song.title)`, which Python compares item by item.
- **A comparison:** a function that's handed two items, `a` and `b`, and answers with a number: below zero when `a` comes first, zero when they tie, above zero when `b` comes first. JavaScript and TypeScript work this way. `b.plays - a.plays` puts the most plays first, and `||` moves on to the title only when the artists tie (when `localeCompare` gives 0).

A note on the languages: `sort` sorts an array in place, so the code sorts a copy, `[...songs]`, and leaves `songs` alone (newer JavaScript also has `toSorted`, which makes the copy for you). C# and Java copy before sorting for the same reason, and Python's `sorted` makes a new list too. One JavaScript trap: called with no comparison, `sort` compares items **as text**, so `[10, 9, 100].sort()` gives `[10, 100, 9]`. Always pass a comparison for numbers.

## The ties in the output

Look at the songs with 340 plays: *Blue Hour*, then *Copper Moon*. And the three with 120: *Amber Road*, *Desert Lights*, *Falling Up*. Within each tie, the songs kept the order they had before the sort, A to Z by title. That's not luck: every sort in that example is stable, C#'s `OrderBy` included.

Stability matters whenever the order you started with means something:

- **Sorting in steps.** Sort a playlist by title, then by artist with a stable sort, and each artist's songs stay in title order: two keys, one sort at a time. That's the two clicks from the bug report.
- **Ties that should stay put.** A leaderboard sorted by points should keep players with equal points in the order they got there, like `addToBoard` in *Exercise: Sort the Leaderboard*.

**Back to the bug report.** The C# app sorted with `List<T>.Sort`, which is unstable: songs by the same artist could come out in either order, and the order could change between refreshes as the list changed. The fix is one of two lines: sort with `OrderBy` (and `ThenBy`), which is stable, or sort by a second key that breaks every tie. Of the sorts you wrote: insertion sort and merge sort are stable (merge sort because it takes from the left pile on a tie, `<=`), while selection sort's long-distance swaps and the in-place quicksort can jump an item past its twin.

**Try it.** Sort the songs by plays, most first, **and** by title within each tie on purpose: in C#, add `.ThenBy(song => song.Title, StringComparer.Ordinal)`; in Python, use `key=lambda song: (-song.plays, song.title)`. The output doesn't change, because the stable sort already kept that order, but now it doesn't depend on the starting order.

## The cost card

| Operation | Big-O | The everyday reason |
|---|---|---|
| Built-in sort, any list | O(n log n) | a tuned mix of merge sort or quicksort with insertion sort |
| Built-in sort, almost sorted (Timsort) | close to O(n) | it finds the stretches already in order and merges them |
| Compare two items by several keys | O(1) for a fixed number of keys | look at the next key only on a tie |
| Extra memory | O(n) for Timsort and `OrderBy`; O(log n) for introsort | merging needs room; quicksort sorts in place |

## Check yourself

2 questions to try on the lesson page.

## So what

In real code, sorting is one line: the built-in sort plus your key or comparison. Your job is to name the keys in the right order and to know whether ties keep their order, because "sorted by plays, then by title" and "sorted by plays, ties in any order" look the same until two songs tie, usually in production, on a list longer than the one you tested.

## Key terms

- [Stable Sort](https://www.ask-codey.com/glossary/stable-sort)
- [Sort Key](https://www.ask-codey.com/glossary/sort-key-data-structures)
- [Sorting Algorithm](https://www.ask-codey.com/glossary/sorting-algorithm)
- [Linearithmic Time](https://www.ask-codey.com/glossary/linearithmic-time)

## Cheat sheets

- [Most Played, Then A to Z: Stable and Built-In Sorts](https://www.ask-codey.com/cheat-sheets/ds-built-in-sort-cheat-sheet)

Source: https://www.ask-codey.com/lessons/ds-built-in-sort
