# A Million Songs to Sort Before Bedtime: Merge Sort

Sort a million songs by title in seconds instead of all night: why the simple sorts take hundreds of billions of comparisons, what splitting the list in half buys, and the sort built on splitting and merging, merge sort, with its price in memory.

Journeyman · Data Structures · Updated November 17, 2026

By Gregor Dzierzon

## After this lesson you can

- Write merge sort: split the list in half, sort each half, merge the sorted halves
- Explain why merge sort takes O(n log n) steps and needs extra memory

## Key takeaways

- Merge sort splits the list in half, sorts each half with merge sort, then merges the two sorted halves into one.
- Merging two sorted piles takes one rule: keep taking the smaller of the two front items.
- There are about log n levels of splitting, and each level merges all n items, so merge sort is O(n log n), however the list starts.
- It needs room for the merged copies: O(n) extra memory.
- For a million songs that's about 20 million steps, against about half a trillion comparisons for selection sort.

**Before this:** *One New Score on a Sorted Leaderboard: Insertion Sort* (on a jumbled list, both simple sorts are O(n²)).

A new user signs up for your music app and imports their library: a million songs, in no order at all. Before the search box can find anything by halving, the library has to be sorted by title, and the user is waiting.

## What would you try?

**Selection sort or insertion sort.** Selection sort compares every pair: about 1,000,000 × 1,000,000 ÷ 2, half a trillion comparisons. Insertion sort does about half that on a jumbled list, still hundreds of billions. At the speeds this module's exercises measured, that's hours even in the fastest of the five languages, and most of a night in Python. The user has gone to bed.

**Split the list in half and sort each half.** Two halves of 500,000 songs, each sorted with selection sort: 500,000 × 500,000 ÷ 2 = 125 billion comparisons each, 250 billion for both. Splitting alone halved the work! But now there are two sorted lists, not one.

**Combine the two sorted halves.** Put them side by side and look at the first song of each. The one that comes first in the alphabet is the first song overall: take it. Look at the two fronts again, take the earlier one, and keep going. Every song is taken once, so combining costs about a million steps, nothing next to 250 billion.

| What we tried | Work for a million songs | Where it breaks |
|---|---|---|
| Selection sort the whole list | about 500,000,000,000 comparisons | it runs all night |
| Sort each half, then combine | about 250,000,000,000 + 1,000,000 | still hundreds of billions |

## The questions that lead to it

**Splitting in half halved the work. What if each half is split again?** Four quarters of 250,000 songs, sorted and combined, is half the work again. And again, and again.

**When do you stop?** When a piece is a single song. A list of one song is already sorted, so there's nothing left to sort at all: only combining.

**How much does all that combining cost?** Combining two sorted piles touches each song once. Every level of splitting has a million songs to combine, about a million steps, and a million halves down to single songs in about 20 levels. So: about 20 levels × a million steps, **about 20 million steps** in all, instead of half a trillion.

## How it got its name

This idea was so useful that it got a name: **merge sort**, because the work is all in the **merge**, combining two sorted piles. Picture sorting a shuffled deck of cards with friends. You split the deck in half and hand each half to a friend. They split theirs and hand them on, until everyone holds a single card, and a single card is already sorted. Then the piles come back together two at a time: look at the top card of each pile, take the smaller one, and repeat. When one pile runs out, the other pile goes on the end as it is.

![A deck of cards being split in half, then in half again, by a row of friends at a table, until each holds one card, then the friends merging their piles back together two at a time into one sorted pile, with arrows showing the split going down and the merge coming back up](https://fsdtrainingmedia.blob.core.windows.net/public/images/2026/11/c958afd878cd478a9d43b8da2636073f.webp)

- **Split** the list in half.
- **Sort each half** with merge sort: the same function, called on a smaller list. A list of one item, or none, is already sorted, and that's the base case that stops the recursion from Module 3.
- **Merge** the two sorted halves into one sorted list.

Solving a problem by cutting it into smaller copies of itself, solving those, and combining the answers has a name too: **divide and conquer**. The next lesson's sort works this way as well.

## Merge sort in code

This code sorts eight cards and prints every merge, so you can watch the piles come back together. It also counts the cards placed while merging:

```csharp
int placed = 0;

string Show(List<int> cards) => "[" + string.Join(", ", cards) + "]";

List<int> MergeSort(List<int> cards)
{
    if (cards.Count <= 1)
    {
        return cards;
    }
    int middle = cards.Count / 2;
    List<int> left = MergeSort(cards.GetRange(0, middle));
    List<int> right = MergeSort(cards.GetRange(middle, cards.Count - middle));

    List<int> merged = new List<int>();
    int l = 0;
    int r = 0;
    while (l < left.Count && r < right.Count)
    {
        if (left[l] <= right[r])
        {
            merged.Add(left[l]);
            l++;
        }
        else
        {
            merged.Add(right[r]);
            r++;
        }
    }
    merged.AddRange(left.GetRange(l, left.Count - l));
    merged.AddRange(right.GetRange(r, right.Count - r));
    placed += merged.Count;
    Console.WriteLine("Merge " + Show(left) + " + " + Show(right) + " -> " + Show(merged));
    return merged;
}

MergeSort(new List<int> { 8, 3, 5, 1, 7, 2, 6, 4 });
Console.WriteLine("Cards placed while merging: " + placed);
```

```text
Merge [8] + [3] -> [3, 8]
Merge [5] + [1] -> [1, 5]
Merge [3, 8] + [1, 5] -> [1, 3, 5, 8]
Merge [7] + [2] -> [2, 7]
Merge [6] + [4] -> [4, 6]
Merge [2, 7] + [4, 6] -> [2, 4, 6, 7]
Merge [1, 3, 5, 8] + [2, 4, 6, 7] -> [1, 2, 3, 4, 5, 6, 7, 8]
Cards placed while merging: 24
```

```java
int placed = 0;

String show(List<Integer> cards) {
    return "[" + cards.stream().map(String::valueOf).collect(Collectors.joining(", ")) + "]";
}

List<Integer> mergeSort(List<Integer> cards) {
    if (cards.size() <= 1) {
        return cards;
    }
    int middle = cards.size() / 2;
    List<Integer> left = mergeSort(new ArrayList<>(cards.subList(0, middle)));
    List<Integer> right = mergeSort(new ArrayList<>(cards.subList(middle, cards.size())));

    List<Integer> merged = new ArrayList<>();
    int l = 0;
    int r = 0;
    while (l < left.size() && r < right.size()) {
        if (left.get(l) <= right.get(r)) {
            merged.add(left.get(l));
            l++;
        } else {
            merged.add(right.get(r));
            r++;
        }
    }
    merged.addAll(left.subList(l, left.size()));
    merged.addAll(right.subList(r, right.size()));
    placed += merged.size();
    IO.println("Merge " + show(left) + " + " + show(right) + " -> " + show(merged));
    return merged;
}

void main() {
    mergeSort(List.of(8, 3, 5, 1, 7, 2, 6, 4));
    IO.println("Cards placed while merging: " + placed);
}
```

```text
Merge [8] + [3] -> [3, 8]
Merge [5] + [1] -> [1, 5]
Merge [3, 8] + [1, 5] -> [1, 3, 5, 8]
Merge [7] + [2] -> [2, 7]
Merge [6] + [4] -> [4, 6]
Merge [2, 7] + [4, 6] -> [2, 4, 6, 7]
Merge [1, 3, 5, 8] + [2, 4, 6, 7] -> [1, 2, 3, 4, 5, 6, 7, 8]
Cards placed while merging: 24
```

```python
placed = 0


def show(cards):
    return "[" + ", ".join(str(card) for card in cards) + "]"


def merge_sort(cards):
    global placed
    if len(cards) <= 1:
        return cards
    middle = len(cards) // 2
    left = merge_sort(cards[:middle])
    right = merge_sort(cards[middle:])

    merged = []
    l = 0
    r = 0
    while l < len(left) and r < len(right):
        if left[l] <= right[r]:
            merged.append(left[l])
            l += 1
        else:
            merged.append(right[r])
            r += 1
    merged += left[l:]
    merged += right[r:]
    placed += len(merged)
    print(f"Merge {show(left)} + {show(right)} -> {show(merged)}")
    return merged


merge_sort([8, 3, 5, 1, 7, 2, 6, 4])
print(f"Cards placed while merging: {placed}")
```

```text
Merge [8] + [3] -> [3, 8]
Merge [5] + [1] -> [1, 5]
Merge [3, 8] + [1, 5] -> [1, 3, 5, 8]
Merge [7] + [2] -> [2, 7]
Merge [6] + [4] -> [4, 6]
Merge [2, 7] + [4, 6] -> [2, 4, 6, 7]
Merge [1, 3, 5, 8] + [2, 4, 6, 7] -> [1, 2, 3, 4, 5, 6, 7, 8]
Cards placed while merging: 24
```

```javascript
let placed = 0;

function show(cards) {
  return `[${cards.join(", ")}]`;
}

function mergeSort(cards) {
  if (cards.length <= 1) {
    return cards;
  }
  const middle = Math.floor(cards.length / 2);
  const left = mergeSort(cards.slice(0, middle));
  const right = mergeSort(cards.slice(middle));

  const merged = [];
  let l = 0;
  let r = 0;
  while (l < left.length && r < right.length) {
    if (left[l] <= right[r]) {
      merged.push(left[l]);
      l++;
    } else {
      merged.push(right[r]);
      r++;
    }
  }
  merged.push(...left.slice(l), ...right.slice(r));
  placed += merged.length;
  console.log(`Merge ${show(left)} + ${show(right)} -> ${show(merged)}`);
  return merged;
}

mergeSort([8, 3, 5, 1, 7, 2, 6, 4]);
console.log(`Cards placed while merging: ${placed}`);
```

```text
Merge [8] + [3] -> [3, 8]
Merge [5] + [1] -> [1, 5]
Merge [3, 8] + [1, 5] -> [1, 3, 5, 8]
Merge [7] + [2] -> [2, 7]
Merge [6] + [4] -> [4, 6]
Merge [2, 7] + [4, 6] -> [2, 4, 6, 7]
Merge [1, 3, 5, 8] + [2, 4, 6, 7] -> [1, 2, 3, 4, 5, 6, 7, 8]
Cards placed while merging: 24
```

```typescript
let placed = 0;

function show(cards: number[]): string {
  return `[${cards.join(", ")}]`;
}

function mergeSort(cards: number[]): number[] {
  if (cards.length <= 1) {
    return cards;
  }
  const middle = Math.floor(cards.length / 2);
  const left = mergeSort(cards.slice(0, middle));
  const right = mergeSort(cards.slice(middle));

  const merged: number[] = [];
  let l = 0;
  let r = 0;
  while (l < left.length && r < right.length) {
    if (left[l]! <= right[r]!) {
      merged.push(left[l]!);
      l++;
    } else {
      merged.push(right[r]!);
      r++;
    }
  }
  merged.push(...left.slice(l), ...right.slice(r));
  placed += merged.length;
  console.log(`Merge ${show(left)} + ${show(right)} -> ${show(merged)}`);
  return merged;
}

mergeSort([8, 3, 5, 1, 7, 2, 6, 4]);
console.log(`Cards placed while merging: ${placed}`);
```

```text
Merge [8] + [3] -> [3, 8]
Merge [5] + [1] -> [1, 5]
Merge [3, 8] + [1, 5] -> [1, 3, 5, 8]
Merge [7] + [2] -> [2, 7]
Merge [6] + [4] -> [4, 6]
Merge [2, 7] + [4, 6] -> [2, 4, 6, 7]
Merge [1, 3, 5, 8] + [2, 4, 6, 7] -> [1, 2, 3, 4, 5, 6, 7, 8]
Cards placed while merging: 24
```

A note on the languages: each one copies a half of the list its own way, `GetRange` in C#, `subList` copied into a new `ArrayList` in Java, and slices (`cards[:middle]`, `cards.slice(0, middle)`) in Python, JavaScript and TypeScript. The `!` after `left[l]` in TypeScript says "this item is there", which the loop's condition guarantees. Python needs `global placed` to change the counter that lives outside the function.

The merges come out in the order the recursion finishes them: the left half of the deck is completely sorted, `[1, 3, 5, 8]`, before the right half starts. The call stack from *Where Do the Waiting Calls Wait? The Call Stack* is what keeps track of which half is waiting.

![The eight cards 8, 3, 5, 1, 7, 2, 6, 4 at the top of a tree, split in half level by level down to eight single cards, then merged back up level by level into [3, 8], [1, 5], [2, 7], [4, 6], then [1, 3, 5, 8] and [2, 4, 6, 7], then [1, 2, 3, 4, 5, 6, 7, 8]: three levels of merging, each placing all 8 cards](https://fsdtrainingmedia.blob.core.windows.net/public/images/2026/11/0c48ca4ba652466ab0a29522aff06720.webp)

## Why it's O(n log n)

Look at the picture as levels. Splitting 8 cards in half, then in half again, reaches single cards after 3 splits: that's the halving count, log n, from *How Many Times Can You Halve a Million? O(log n)*. On the way back up, every level merges all 8 cards once: 8 at the bottom level (four merges of 2), 8 in the middle (two merges of 4), and 8 at the top. Three levels of 8 cards is the 24 cards placed.

So merge sort's work is n cards × log n levels: **O(n log n)**, read "big O of n log n", the speed from *Sorting a Million Songs, and the Playlist You Can't Compute: O(n log n) and O(2ⁿ)*. For a million songs that's about 20 million steps, against about 500 billion for selection sort: the imported library is sorted before the user has put the kettle on. This module's last exercise measured it on 50,000 songs: about 0.15 seconds in Python, where insertion sort takes about a minute. And unlike insertion sort, merge sort has no bad day: it splits and merges the same way whatever order the list starts in.

The price is memory. Every merge builds a new list to hold its result, so merge sort needs room for about n extra items: **O(n) extra memory**. The simple sorts needed O(1). On a laptop sorting a million songs that's nothing; on a phone that's short of memory, it's the problem the next lesson starts from.

## When something else wins

- **A list that's already almost in order.** Insertion sort does close to n comparisons there, and merge sort still does all its n log n. The built-in sorts in Java, Python and JavaScript use both: they look for stretches already in order, sort short stretches by insertion, and merge the rest.
- **Very little memory.** Merge sort's second copy can be too much, which is where *Sorting Without a Second Copy: Quicksort* comes in.

**Try it.** Add a ninth card, 9, to the end of the list. How many merges are there now? (Eight: each merge turns two piles into one, so it takes one merge fewer than there are cards to get from nine piles to one.)

## The cost card

| Operation | Big-O | The everyday reason |
|---|---|---|
| Sort, any starting order | O(n log n) | about log n levels of splitting, and each level merges all n cards |
| Merge two sorted piles | O(n) | each card is taken from the top of a pile once |
| Extra memory | O(n) | the merged piles need a table of their own |

## Check yourself

2 questions to try on the lesson page.

## So what

Merge sort shows the trick behind every fast sort: cut the problem in half, solve the halves, and combine. That turns O(n²) into O(n log n), the difference between a sort that finishes before you blink and one that runs all night.

## Key terms

- [Merge Sort](https://www.ask-codey.com/glossary/merge-sort)
- [Divide and Conquer](https://www.ask-codey.com/glossary/divide-and-conquer)
- [Linearithmic Time](https://www.ask-codey.com/glossary/linearithmic-time)
- [Recursion](https://www.ask-codey.com/glossary/recursion-data-structures)

## Cheat sheets

- [A Million Songs to Sort Before Bedtime: Merge Sort](https://www.ask-codey.com/cheat-sheets/ds-merge-sort-cheat-sheet)

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