# One New Score on a Sorted Leaderboard: Insertion Sort

Keep a 10,000-player leaderboard in order as a new score arrives every few seconds, without sorting it all again: why re-sorting falls short, and the sort built on one slide, insertion sort, which is also fast on any list that's almost in order.

Apprentice · Data Structures · Updated November 17, 2026

By Gregor Dzierzon

## After this lesson you can

- Trace insertion sort pass by pass on a short list
- Explain why insertion sort is O(n²) at worst but fast on a list that's almost sorted
- Choose between sorting again and sliding a new item into place, or between selection and insertion sort, and say why

## Key takeaways

- Insertion sort takes the next item and slides it left, past every bigger item, into its place in the sorted part.
- On a backward list every item slides all the way: n(n - 1) ÷ 2 comparisons, so its worst case is O(n²).
- On a list that's already sorted, each item needs one comparison, so its best case is O(n), and an almost sorted list is nearly that fast.
- One new score on a sorted board of 10,000 is a single slide, at most 10,000 steps, instead of about 50 million comparisons to sort it all again.

**Before this:** *Putting the Leaderboard in Order: Selection Sort* (sorting 10,000 players takes about 50 million comparisons, even when only one score changed).

The time trial's leaderboard is sorted: 10,000 lap times, fastest first. Now the game goes live. A new lap time arrives every few seconds, and the board has to show it in its place straight away, so the driver sees where they finished.

## What would you try?

**Add it to the end and sort again.** With selection sort, that's 10,001 times compared pair by pair: about 50 million comparisons, every few seconds, to place one time. That's O(n²) per score.

**Sort only when someone opens the board.** The same 50 million comparisons, paid later. On a busy game someone always has the board open, so nothing is saved.

**Find its place and move the slower times down one.** Start at the slow end: is the new time faster than the slowest? Then that time moves down a place to make room. Keep going until you reach a time faster than the new one, and drop it into the gap. At most 10,000 comparisons and moves, and usually far fewer. That's O(n) per score.

| What we tried | Work for one new score | Where it breaks |
|---|---|---|
| Add it and sort again | about 50,000,000 comparisons | every few seconds, the whole board again |
| Sort when the board is opened | the same, paid later | the board is always open |
| Find its place, move the slower ones down | at most 10,000 steps | only on a board that's already sorted |

## The questions that lead to it

**What does the board do most?** Take one new time, again and again. **What's already true?** Everything else is in order. The re-sorts threw that away and checked every pair again.

**When you're dealt one more card, do you re-sort your whole hand?** No: you slide it into place among the cards you're already holding. Your hand is always sorted, so one slide is all it takes.

So what if a whole sort did only that? Start with one card in your hand, then pick up the next and slide it into place, then the next, until the deck is gone.

## How it got its name

This idea was so useful that it got a name: **insertion sort**, because it **inserts** each item into its place among the ones already sorted. It's the simple sort working developers meet most, often without knowing it: the built-in sorts in Java, Python and JavaScript switch to it for short stretches of a list.

![A hand of five playing cards fanned out, already in order 3, 5, 8, 9 and J, and a sixth card, a 7, being slid in between the 5 and the 8, with a curved arrow showing where it goes](https://fsdtrainingmedia.blob.core.windows.net/public/images/2026/11/840da92132314963b5c4a2a5934819cc.webp)

In a list, insertion sort does the card move in place:

- The **sorted part** starts as only the first item.
- Each **pass** takes the next item, the first of the unsorted part, and compares it with the items to its left.
- Every item bigger than it moves one place right, making room, and it drops into the gap.

## Insertion sort in code

Here are the same six lap times as in *Putting the Leaderboard in Order: Selection Sort*, sorted fastest first, with the list printed after every pass:

```csharp
int[] times = { 52, 38, 47, 31, 44, 59 };

for (int pass = 1; pass < times.Length; pass++)
{
    int current = times[pass];
    int i = pass - 1;
    while (i >= 0 && times[i] > current)
    {
        times[i + 1] = times[i];
        i--;
    }
    times[i + 1] = current;
    Console.WriteLine("Pass " + pass + ": " + string.Join(" ", times));
}
```

```text
Pass 1: 38 52 47 31 44 59
Pass 2: 38 47 52 31 44 59
Pass 3: 31 38 47 52 44 59
Pass 4: 31 38 44 47 52 59
Pass 5: 31 38 44 47 52 59
```

```java
void main() {
    int[] times = {52, 38, 47, 31, 44, 59};

    for (int pass = 1; pass < times.length; pass++) {
        int current = times[pass];
        int i = pass - 1;
        while (i >= 0 && times[i] > current) {
            times[i + 1] = times[i];
            i--;
        }
        times[i + 1] = current;
        IO.println("Pass " + pass + ": " + Arrays.stream(times).mapToObj(String::valueOf).collect(Collectors.joining(" ")));
    }
}
```

```text
Pass 1: 38 52 47 31 44 59
Pass 2: 38 47 52 31 44 59
Pass 3: 31 38 47 52 44 59
Pass 4: 31 38 44 47 52 59
Pass 5: 31 38 44 47 52 59
```

```python
times = [52, 38, 47, 31, 44, 59]

for pass_number in range(1, len(times)):
    current = times[pass_number]
    i = pass_number - 1
    while i >= 0 and times[i] > current:
        times[i + 1] = times[i]
        i -= 1
    times[i + 1] = current
    print(f"Pass {pass_number}: " + " ".join(str(time) for time in times))
```

```text
Pass 1: 38 52 47 31 44 59
Pass 2: 38 47 52 31 44 59
Pass 3: 31 38 47 52 44 59
Pass 4: 31 38 44 47 52 59
Pass 5: 31 38 44 47 52 59
```

```javascript
const times = [52, 38, 47, 31, 44, 59];

for (let pass = 1; pass < times.length; pass++) {
  const current = times[pass];
  let i = pass - 1;
  while (i >= 0 && times[i] > current) {
    times[i + 1] = times[i];
    i--;
  }
  times[i + 1] = current;
  console.log(`Pass ${pass}: ${times.join(" ")}`);
}
```

```text
Pass 1: 38 52 47 31 44 59
Pass 2: 38 47 52 31 44 59
Pass 3: 31 38 47 52 44 59
Pass 4: 31 38 44 47 52 59
Pass 5: 31 38 44 47 52 59
```

```typescript
const times: number[] = [52, 38, 47, 31, 44, 59];

for (let pass = 1; pass < times.length; pass++) {
  const current = times[pass];
  let i = pass - 1;
  while (i >= 0 && times[i] > current) {
    times[i + 1] = times[i];
    i--;
  }
  times[i + 1] = current;
  console.log(`Pass ${pass}: ${times.join(" ")}`);
}
```

```text
Pass 1: 38 52 47 31 44 59
Pass 2: 38 47 52 31 44 59
Pass 3: 31 38 47 52 44 59
Pass 4: 31 38 44 47 52 59
Pass 5: 31 38 44 47 52 59
```

The `while` loop is the slide. It walks left from the item's old spot, moving each bigger time one place right, and stops at the first time that isn't bigger, or at the start of the list. The order of its two checks matters: `i >= 0` comes first, so the code never reads `times[-1]`.

Compare the passes with selection sort's. Pass 3 slides 31 all the way to the front, past three bigger times. Pass 5 looks at 59, sees that 52 isn't bigger, and stops after one comparison: 59 was already in place.

![The six lap times 52, 38, 47, 31, 44 and 59 drawn as six cards in a row, shown six times: the starting order, then after each of the five passes. In each row the sorted part on the left is shaded, the card that pass picked up is outlined, and an arrow shows how far left it slid, until the row reads 31, 38, 44, 47, 52, 59](https://fsdtrainingmedia.blob.core.windows.net/public/images/2026/11/bfabfc118a2a4ca685671b7c918055a7.webp)

## Slow on a backward list, fast on an almost sorted one

How much work insertion sort does depends on the list it's given, which selection sort's didn't. This code counts the comparisons, the `times[i] > current` checks, for four lists of the same six times:

```csharp
int Comparisons(int[] start)
{
    int[] times = (int[])start.Clone();
    int comparisons = 0;
    for (int pass = 1; pass < times.Length; pass++)
    {
        int current = times[pass];
        int i = pass - 1;
        while (i >= 0)
        {
            comparisons++;
            if (times[i] <= current)
            {
                break;
            }
            times[i + 1] = times[i];
            i--;
        }
        times[i + 1] = current;
    }
    return comparisons;
}

Console.WriteLine("Backward: " + Comparisons(new int[] { 59, 52, 47, 44, 38, 31 }) + " comparisons");
Console.WriteLine("Shuffled: " + Comparisons(new int[] { 52, 38, 47, 31, 44, 59 }) + " comparisons");
Console.WriteLine("Almost sorted: " + Comparisons(new int[] { 31, 38, 44, 52, 47, 59 }) + " comparisons");
Console.WriteLine("Already sorted: " + Comparisons(new int[] { 31, 38, 44, 47, 52, 59 }) + " comparisons");
```

```text
Backward: 15 comparisons
Shuffled: 10 comparisons
Almost sorted: 6 comparisons
Already sorted: 5 comparisons
```

```java
int comparisons(int[] start) {
    int[] times = start.clone();
    int comparisons = 0;
    for (int pass = 1; pass < times.length; pass++) {
        int current = times[pass];
        int i = pass - 1;
        while (i >= 0) {
            comparisons++;
            if (times[i] <= current) {
                break;
            }
            times[i + 1] = times[i];
            i--;
        }
        times[i + 1] = current;
    }
    return comparisons;
}

void main() {
    IO.println("Backward: " + comparisons(new int[] {59, 52, 47, 44, 38, 31}) + " comparisons");
    IO.println("Shuffled: " + comparisons(new int[] {52, 38, 47, 31, 44, 59}) + " comparisons");
    IO.println("Almost sorted: " + comparisons(new int[] {31, 38, 44, 52, 47, 59}) + " comparisons");
    IO.println("Already sorted: " + comparisons(new int[] {31, 38, 44, 47, 52, 59}) + " comparisons");
}
```

```text
Backward: 15 comparisons
Shuffled: 10 comparisons
Almost sorted: 6 comparisons
Already sorted: 5 comparisons
```

```python
def comparisons(start):
    times = list(start)
    count = 0
    for pass_number in range(1, len(times)):
        current = times[pass_number]
        i = pass_number - 1
        while i >= 0:
            count += 1
            if times[i] <= current:
                break
            times[i + 1] = times[i]
            i -= 1
        times[i + 1] = current
    return count


print(f"Backward: {comparisons([59, 52, 47, 44, 38, 31])} comparisons")
print(f"Shuffled: {comparisons([52, 38, 47, 31, 44, 59])} comparisons")
print(f"Almost sorted: {comparisons([31, 38, 44, 52, 47, 59])} comparisons")
print(f"Already sorted: {comparisons([31, 38, 44, 47, 52, 59])} comparisons")
```

```text
Backward: 15 comparisons
Shuffled: 10 comparisons
Almost sorted: 6 comparisons
Already sorted: 5 comparisons
```

```javascript
function comparisons(start) {
  const times = [...start];
  let count = 0;
  for (let pass = 1; pass < times.length; pass++) {
    const current = times[pass];
    let i = pass - 1;
    while (i >= 0) {
      count++;
      if (times[i] <= current) {
        break;
      }
      times[i + 1] = times[i];
      i--;
    }
    times[i + 1] = current;
  }
  return count;
}

console.log(`Backward: ${comparisons([59, 52, 47, 44, 38, 31])} comparisons`);
console.log(`Shuffled: ${comparisons([52, 38, 47, 31, 44, 59])} comparisons`);
console.log(`Almost sorted: ${comparisons([31, 38, 44, 52, 47, 59])} comparisons`);
console.log(`Already sorted: ${comparisons([31, 38, 44, 47, 52, 59])} comparisons`);
```

```text
Backward: 15 comparisons
Shuffled: 10 comparisons
Almost sorted: 6 comparisons
Already sorted: 5 comparisons
```

```typescript
function comparisons(start: number[]): number {
  const times = [...start];
  let count = 0;
  for (let pass = 1; pass < times.length; pass++) {
    const current = times[pass];
    let i = pass - 1;
    while (i >= 0) {
      count++;
      if (times[i] <= current) {
        break;
      }
      times[i + 1] = times[i];
      i--;
    }
    times[i + 1] = current;
  }
  return count;
}

console.log(`Backward: ${comparisons([59, 52, 47, 44, 38, 31])} comparisons`);
console.log(`Shuffled: ${comparisons([52, 38, 47, 31, 44, 59])} comparisons`);
console.log(`Almost sorted: ${comparisons([31, 38, 44, 52, 47, 59])} comparisons`);
console.log(`Already sorted: ${comparisons([31, 38, 44, 47, 52, 59])} comparisons`);
```

```text
Backward: 15 comparisons
Shuffled: 10 comparisons
Almost sorted: 6 comparisons
Already sorted: 5 comparisons
```

This version writes the slide as a loop with a `break`, so every comparison is counted, including the last one that stops the slide.

- **The worst case, a backward list:** every time is smaller than all the times before it, so it slides all the way to the front. That's 1 + 2 + 3 + 4 + 5 = 15 comparisons, the same n(n − 1) ÷ 2 as selection sort: **O(n²)**.
- **The best case, a sorted list:** each time is compared once with its left neighbor, sees it isn't smaller, and stays. That's n − 1 comparisons: **O(n)**, linear time.
- **Almost sorted:** only the times out of place slide, and not far. Six comparisons, close to the best case.

On average, over shuffled lists, an item slides about halfway, which is still O(n²). So both simple sorts are O(n²) in general. The difference is that insertion sort does less work the closer the list already is to sorted, and real data often is: yesterday's leaderboard with today's few new scores, a playlist with one song moved. That's why fast built-in sorts hand short or nearly sorted stretches to insertion sort.

**Try it.** Add a seventh time, 30, to the end of the already sorted list. How many comparisons now? It has to slide past all six, so 5 + 6 = 11.

## Back to the live board

That **Try it** is the live leaderboard in miniature. A sorted board with one new time at the end is the most nearly sorted list there is: every time but the new one is already in place, so insertion sort does exactly one slide. On the 10,000-player board that's at most 10,000 steps per new score, against about 50 million for sorting it all again with selection sort.

Two honest limits:

- **The slide is still O(n).** You could find the new time's place by halving, about 14 looks in 10,000, but the slower times still have to move down to make room. When scores pour in many times a second on a board of millions, that moving adds up, and Module 6's trees and heaps keep things in order without sliding.
- **A big jumbled list is still O(n²).** Insertion sort shines when the list is nearly in order. Hand it a million shuffled songs and it's as hopeless as selection sort, which is where the next chapter starts.

## The cost card

| Operation | Big-O | The everyday reason |
|---|---|---|
| Sort, worst case (backward) | O(n²) | every new card slides past every card you hold |
| Sort, average case | O(n²) | each card slides about halfway |
| Sort, best case (already sorted) | O(n) | each new card is already bigger than the last one you hold |
| Add one item to a sorted list | O(n) | one slide, at most past every item |
| Extra memory | O(1) | it sorts in place, holding one card at a time |

## Check yourself

2 questions to try on the lesson page.

## So what

Insertion sort is the simple sort worth keeping: O(n²) on a jumbled list, but nearly O(n) on one that's almost in order, and its single slide is the right way to add one score to a sorted leaderboard. For big jumbled lists, though, both simple sorts are too slow, and the next chapter finds sorts that are O(n log n).

## Key terms

- [Insertion Sort](https://www.ask-codey.com/glossary/insertion-sort)
- [Quadratic Time](https://www.ask-codey.com/glossary/quadratic-time)
- [Best Case](https://www.ask-codey.com/glossary/best-case)
- [Worst Case](https://www.ask-codey.com/glossary/worst-case)

## Cheat sheets

- [One New Score on a Sorted Leaderboard: Insertion Sort](https://www.ask-codey.com/cheat-sheets/ds-insertion-sort-cheat-sheet)

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