# Sorting & Searching, Explained

> How computers find things fast and put things in order: linear vs. binary search, then the classic sorts - bubble, merge, and quick - with the intuition behind each one's speed, not just the code.


---

# Sorting & Searching, Explained

You already call `.sort()` and `in` without thinking twice. That's fine for most code - but the moment
something is slow, or an interviewer asks "how would you find this faster," you need the picture underneath
the built-in. Two questions drive almost everything here: *how do I find a value fast?* and *how do I put
things in order in the first place?* Each answer builds on the one before it - sorting exists partly to make
searching faster.

This guide keeps the code in Python so you can run every example as you read.

## How to read this

Read in order - binary search only makes sense once you've felt *why* linear search is slow, and every sort
after bubble sort is really "here's a cleverer way to avoid bubble sort's problem."

## The phases

1. **[Linear vs. Binary Search](01-linear-vs-binary-search.md)** - the two ways to find a value, and why
   sorted order unlocks a dramatically faster search.
2. **[Binary Search, Implemented](02-binary-search-implemented.md)** - the real algorithm on a sorted array,
   its complexity, and the off-by-one bugs that catch almost everyone once.
3. **[Bubble Sort](03-bubble-sort.md)** - the simplest sort there is: compare neighbors, swap, repeat. Slow,
   but it builds the intuition every other sort refines.
4. **[Merge Sort (and Quick Sort)](04-merge-sort-and-quick-sort.md)** - divide and conquer: split the problem
   in half, solve the halves, combine. The shape behind every fast general-purpose sort.


---

# Linear vs. Binary Search

Searching sounds trivial - "is this value in here?" - but *how* you search is one of the highest-leverage
choices you'll make in everyday code. There are two fundamentally different strategies, and which one you
can use depends on a single fact: is the data sorted?

## Linear search: check everything

**What it actually is.** Start at the front, look at each item, stop when you find a match (or run out of
items). No assumptions about order - it works on any collection, sorted or not.

```python runnable
def linear_search(items, target):
    for i, value in enumerate(items):
        if value == target:
            return i
    return -1

scores = [91, 47, 68, 12, 85, 33]
print(linear_search(scores, 85))
print(linear_search(scores, 100))
```
```console
4
-1
```
*What just happened:* `linear_search` walks the list from the front, comparing each value to `85` until it
finds it at index `4`. Looking for `100` walks the *entire* list and finds nothing, returning `-1`. Either
way, the cost scales directly with how many items you check - this is the `O(n)` "linear" shape from Big-O:
double the list, and in the worst case you double the work.

💡 **Key point.** Linear search is the only option when the data isn't sorted - you genuinely have no
shortcut, because any item could be the one you want. It's also perfectly fine for small collections; the
cost only bites once `n` gets large.

## Binary search: exploit sorted order

**What it actually is.** If the data is *sorted*, you don't need to check everything. Check the middle item.
If your target is smaller, it can only be in the left half - the entire right half is eliminated in one
comparison. If it's bigger, the left half is eliminated instead. Repeat on the remaining half.

Think of a sorted phone book. You don't start at "Aardvark" and read every name - you flip to the middle,
see you've landed on "M," and know immediately whether "Grace" is to the left or right. Each flip throws away
half of what's left.

```text
   ["Ada","Alan","Bob","Grace","Linus","Margaret","Xu"]   ← looking for "Grace"
    check middle → "Grace" is at or before "Grace"? → keep the LEFT half
   ["Ada","Alan","Bob","Grace"]
    check middle → keep narrowing...
   found in a handful of steps, not seven
```

*What just happened:* every comparison eliminates half the remaining candidates, not just one item. For a
list of a million sorted names, that's about 20 comparisons to find - or rule out - any value. This is the
`O(log n)` "logarithmic" shape: doubling the data adds just *one* more comparison. (See
[Big-O Without the Math Panic](/guides/big-o-without-the-math-panic) if `O(log n)` is new to you.)

⚠️ **Gotcha.** Binary search only works because the data is sorted. Run it on an unsorted list and it will
silently give you wrong answers - it'll happily discard the half your target is actually sitting in, because
it trusts an ordering that isn't there. If your data isn't sorted and you only need to search it once, sorting
first (`O(n log n)`, see Phase 4) plus one binary search is often still cheaper than repeated linear scans -
but if you're searching a fixed list many times, sort it once and reuse that sorted order every time.

## Why this trade-off exists

Linear search needs nothing extra - no sorting, no setup - and it's the only choice for unordered data. Binary
search needs the data sorted *first*, but once it is, every subsequent search is dramatically cheaper. That's
the recurring theme of this whole guide: sorting is an investment that makes every future search cheap.

```quiz
[
  {
    "q": "What does linear search require that binary search doesn't?",
    "choices": ["A sorted collection", "Nothing extra - it works on any order", "A hash map", "A recursive function"],
    "answer": 1,
    "explain": "Linear search checks every item in whatever order they're in - it makes no assumptions, which is also why it can't skip anything."
  },
  {
    "q": "Binary search eliminates how much of the remaining data on each comparison?",
    "choices": ["One item", "About half", "It depends on the data", "All but the last item"],
    "answer": 1,
    "explain": "Comparing against the middle item throws away the half that can't contain the target - that halving is what makes it O(log n)."
  },
  {
    "q": "What happens if you run binary search on an unsorted list?",
    "choices": ["It runs slower but still works", "It throws an error", "It can silently return the wrong answer", "It automatically sorts the list first"],
    "answer": 2,
    "explain": "Binary search trusts the ordering to decide which half to discard - if that ordering isn't real, it can discard the half your target is actually in."
  }
]
```


---

# Binary Search, Implemented

Phase 1 gave you the idea: keep halving. This phase writes it as real, correct code - and walks through the
exact bugs that catch people the first time they implement it themselves.

## The iterative version

Keep two pointers, `lo` and `hi`, marking the range you still need to search. Each step checks the middle;
if it's not a match, you shrink the range to whichever half could still contain the target.

```python runnable
def binary_search(items, target):
    lo, hi = 0, len(items) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

names = ["Ada", "Alan", "Grace", "Linus", "Margaret", "Xu"]
print(binary_search(names, "Linus"))
print(binary_search(names, "Bob"))
```
```console
3
-1
```
*What just happened:* `lo` and `hi` start at the two ends of the list. Each loop checks `items[mid]`: an
exact match returns immediately; too small means the target must be to the right, so `lo` moves past `mid`;
too big means it must be to the left, so `hi` moves before `mid`. The loop keeps shrinking the range until
either it finds the target or `lo` crosses `hi` - meaning the range is empty and the target isn't present.

## The complexity: O(log n)

Every iteration cuts the range roughly in half, so the loop runs about `log₂(n)` times before it either
finds the target or the range empties out. For a million items, that's about 20 iterations - not a million.
That's the entire reason binary search exists: turning a search that gets slower as data grows into one that
barely notices.

## The same search, in other languages

The logic does not change when the language does: two pointers, a midpoint, halve the range. Here is the
exact same iterative binary search in seven languages. Flip between the tabs and notice how little the shape
actually shifts - the typed languages just spell out the array and integer types the dynamic ones leave
implied.

[[codegroup Binary Search]]

```python
def binary_search(items, target):
    lo, hi = 0, len(items) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1
```

```javascript
function binarySearch(items, target) {
  let lo = 0, hi = items.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (items[mid] === target) return mid;
    if (items[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}
```

```typescript
function binarySearch(items: number[], target: number): number {
  let lo = 0, hi = items.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (items[mid] === target) return mid;
    if (items[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}
```

```java
static int binarySearch(int[] items, int target) {
    int lo = 0, hi = items.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (items[mid] == target) return mid;
        if (items[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}
```

```cpp
int binary_search(const std::vector<int>& items, int target) {
    int lo = 0, hi = (int)items.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (items[mid] == target) return mid;
        if (items[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}
```

```go
func binarySearch(items []int, target int) int {
    lo, hi := 0, len(items)-1
    for lo <= hi {
        mid := lo + (hi-lo)/2
        if items[mid] == target {
            return mid
        } else if items[mid] < target {
            lo = mid + 1
        } else {
            hi = mid - 1
        }
    }
    return -1
}
```

```rust
fn binary_search(items: &[i32], target: i32) -> i32 {
    let (mut lo, mut hi) = (0i32, items.len() as i32 - 1);
    while lo <= hi {
        let mid = lo + (hi - lo) / 2;
        let value = items[mid as usize];
        if value == target {
            return mid;
        } else if value < target {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    -1
}
```

[[/codegroup]]

Every version writes the midpoint as `lo + (hi - lo) / 2` rather than `(lo + hi) / 2`. In Python that is
habit; in the fixed-integer languages below it is the difference between correct and a silent overflow bug on
very large arrays, which is the next thing worth knowing.

## The classic off-by-one gotchas

Binary search is short, which is exactly why small mistakes are easy to make and hard to spot. Three to
watch for:

⚠️ **Wrong loop condition: `<` instead of `<=`.** If you write `while lo < hi:` instead of `while lo <= hi:`,
you'll miss the case where the target is exactly at the last remaining index - a single-element range
(`lo == hi`) never gets checked, and a valid target can be reported as missing.

⚠️ **Forgetting to move past `mid`.** If a mismatch sets `lo = mid` (instead of `mid + 1`) or `hi = mid`
(instead of `mid - 1`), the range never shrinks on that side, and the loop can spin forever comparing the
same middle value over and over.

⚠️ **Midpoint overflow (mostly a lower-level-language concern).** `(lo + hi) // 2` is fine in Python - integers
don't overflow - but in languages with fixed-size integers (C, Java), `lo + hi` can itself overflow before
the division happens, for large enough indices. The safer, equivalent form is `lo + (hi - lo) // 2`. Worth
knowing even in Python, since it's the version you'll see in other languages' standard libraries.

```python runnable
# a broken variant: forgets to move past mid on a miss
def broken_search(items, target):
    lo, hi = 0, len(items) - 1
    steps = 0
    while lo <= hi and steps < 5:   # capped so this demo doesn't actually hang
        steps += 1
        mid = (lo + hi) // 2
        if items[mid] == target:
            return mid, steps
        elif items[mid] < target:
            lo = mid            # bug: should be mid + 1
        else:
            hi = mid - 1
    return -1, steps

print(broken_search([1, 2, 3, 4, 5], 5))
```
```console
(-1, 5)
```
*What just happened:* because `lo = mid` never actually moves past the checked index, the search keeps
re-checking a range that never shrinks on the low side. The demo caps it at 5 steps so it terminates and
shows you the failure instead of hanging - a real, unbounded version of this bug is an infinite loop.

## Recursive version, briefly

The same idea also reads naturally as recursion (see
[Recursion, Finally](/guides/recursion-finally-clicks) if that's new to you): shrink the range, and hand the
smaller range to a call of yourself, trusting it to handle the rest.

```python runnable
def binary_search_recursive(items, target, lo=0, hi=None):
    if hi is None:
        hi = len(items) - 1
    if lo > hi:
        return -1
    mid = (lo + hi) // 2
    if items[mid] == target:
        return mid
    elif items[mid] < target:
        return binary_search_recursive(items, target, mid + 1, hi)
    else:
        return binary_search_recursive(items, target, lo, mid - 1)

print(binary_search_recursive([1, 3, 5, 7, 9, 11], 7))
```
```console
3
```
Both versions do the same work in the same `O(log n)` time - the iterative form avoids the (small, but real)
overhead of extra function calls, which is why it's the more common choice in practice.

```quiz
[
  {
    "q": "Why does binary search run in O(log n) instead of O(n)?",
    "choices": ["It checks fewer items by luck", "Each comparison halves the remaining search range", "It skips every other item", "It only works on small lists"],
    "answer": 1,
    "explain": "Halving the range every step means the number of steps grows only with log₂(n), not n itself."
  },
  {
    "q": "What bug does forgetting to set `lo = mid + 1` (using `lo = mid` instead) cause?",
    "choices": ["It searches the wrong half entirely", "The range never shrinks on that side, risking an infinite loop", "It only affects the very first comparison", "Nothing - the result is still correct"],
    "answer": 1,
    "explain": "If lo stays at mid instead of moving past it, the same middle index can be re-checked forever without the range ever narrowing."
  },
  {
    "q": "Why is `lo + (hi - lo) // 2` sometimes preferred over `(lo + hi) // 2`?",
    "choices": ["It's faster in Python", "It avoids integer overflow in languages with fixed-size integers", "It rounds differently and is more accurate", "It works for unsorted lists too"],
    "answer": 1,
    "explain": "In languages without Python's arbitrary-precision integers, lo + hi can overflow before the division happens for large indices; the rewritten form avoids that."
  }
]
```


---

# Bubble Sort: Compare, Swap, Repeat

Sorting is the other half of this guide's story: binary search needs sorted data, so now let's actually put
things in order. Bubble sort is the easiest sort to understand and the easiest to trust is correct - which
makes it the right place to build the intuition, even though it's not what you'd reach for in real code.

## The mental model: neighbors swap until nobody needs to

**What it actually is.** Walk the list left to right, comparing each pair of neighbors. If they're out of
order, swap them. By the end of one full pass, the largest value has been pushed ("bubbled") all the way to
the end. Do another pass, and the next-largest lands in place. Keep going until a full pass makes zero swaps
- that's your signal the list is sorted.

```python runnable
def bubble_sort(items):
    items = items[:]              # work on a copy, don't mutate the caller's list
    n = len(items)
    for pass_num in range(n - 1):
        swapped = False
        for i in range(n - 1 - pass_num):
            if items[i] > items[i + 1]:
                items[i], items[i + 1] = items[i + 1], items[i]
                swapped = True
        if not swapped:           # a pass with no swaps means it's already sorted
            break
    return items

print(bubble_sort([5, 2, 9, 1, 5, 6]))
```
```console
[1, 2, 5, 5, 6, 9]
```
*What just happened:* the first pass compares `(5,2)` → swap, `(5,9)` → no swap, `(9,1)` → swap, `(1,5)` →
no swap, `(5,6)` → no swap - and `9`, the biggest value, has bubbled to the last slot. Each subsequent pass
repeats the walk over a slightly shorter range (the tail is already sorted, so `n - 1 - pass_num` shrinks the
comparison window), placing the next-biggest value correctly, until a pass swaps nothing at all.

💡 **Key point.** The `swapped` flag is a cheap but real optimization: on an already-sorted (or
nearly-sorted) list, bubble sort notices immediately and stops early instead of grinding through every
possible pass.

The compare-and-swap shape barely changes from language to language. Here is the same early-exit bubble
sort in seven of them, each working on its own copy so the caller's list is left untouched:

[[codegroup Bubble Sort]]

```python
def bubble_sort(items):
    items = items[:]
    n = len(items)
    for p in range(n - 1):
        swapped = False
        for i in range(n - 1 - p):
            if items[i] > items[i + 1]:
                items[i], items[i + 1] = items[i + 1], items[i]
                swapped = True
        if not swapped:
            break
    return items
```

```javascript
function bubbleSort(input) {
  const items = [...input];
  const n = items.length;
  for (let p = 0; p < n - 1; p++) {
    let swapped = false;
    for (let i = 0; i < n - 1 - p; i++) {
      if (items[i] > items[i + 1]) {
        [items[i], items[i + 1]] = [items[i + 1], items[i]];
        swapped = true;
      }
    }
    if (!swapped) break;
  }
  return items;
}
```

```typescript
function bubbleSort(input: number[]): number[] {
  const items = [...input];
  const n = items.length;
  for (let p = 0; p < n - 1; p++) {
    let swapped = false;
    for (let i = 0; i < n - 1 - p; i++) {
      if (items[i] > items[i + 1]) {
        [items[i], items[i + 1]] = [items[i + 1], items[i]];
        swapped = true;
      }
    }
    if (!swapped) break;
  }
  return items;
}
```

```java
static int[] bubbleSort(int[] input) {
    int[] items = input.clone();
    int n = items.length;
    for (int p = 0; p < n - 1; p++) {
        boolean swapped = false;
        for (int i = 0; i < n - 1 - p; i++) {
            if (items[i] > items[i + 1]) {
                int tmp = items[i];
                items[i] = items[i + 1];
                items[i + 1] = tmp;
                swapped = true;
            }
        }
        if (!swapped) break;
    }
    return items;
}
```

```cpp
std::vector<int> bubble_sort(std::vector<int> items) {
    int n = (int)items.size();
    for (int p = 0; p < n - 1; p++) {
        bool swapped = false;
        for (int i = 0; i < n - 1 - p; i++) {
            if (items[i] > items[i + 1]) {
                std::swap(items[i], items[i + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;
    }
    return items;
}
```

```go
func bubbleSort(input []int) []int {
    items := append([]int(nil), input...)
    n := len(items)
    for p := 0; p < n-1; p++ {
        swapped := false
        for i := 0; i < n-1-p; i++ {
            if items[i] > items[i+1] {
                items[i], items[i+1] = items[i+1], items[i]
                swapped = true
            }
        }
        if !swapped {
            break
        }
    }
    return items
}
```

```rust
fn bubble_sort(input: &[i32]) -> Vec<i32> {
    let mut items = input.to_vec();
    let n = items.len();
    for p in 0..n.saturating_sub(1) {
        let mut swapped = false;
        for i in 0..n - 1 - p {
            if items[i] > items[i + 1] {
                items.swap(i, i + 1);
                swapped = true;
            }
        }
        if !swapped {
            break;
        }
    }
    items
}
```

[[/codegroup]]

## Why it's O(n²)

**What it actually is.** In the worst case (data sorted backwards), every pass makes close to `n`
comparisons, and you need close to `n` passes to fully sort. That's roughly `n × n` = `n²` comparisons total.
Double the list, and the work roughly *quadruples* - the same nested-loop shape from
[Big-O Without the Math Panic](/guides/big-o-without-the-math-panic).

```mermaid
flowchart LR
  A["Pass 1: compare n-1 pairs"] --> B["Pass 2: compare n-2 pairs"] --> C["Pass 3: compare n-3 pairs"] --> D["... up to n-1 passes"]
```

⚠️ **Gotcha.** Bubble sort's `O(n²)` cost is fine for a few dozen items and genuinely bad for a few hundred
thousand - the kind of slowdown that feels instant in a test and grinds in production. It's taught because
the "compare and swap" idea is the seed every faster sort builds on, not because you should reach for it in
real code (Python's built-in `sorted()` is a well-tuned `O(n log n)` sort - see the next phase for why that
matters).

Try it yourself - step through a shuffle and watch which pairs swap:

```playground-sorting
```

```quiz
[
  {
    "q": "What does one full pass of bubble sort guarantee?",
    "choices": ["The whole list is sorted", "The largest remaining value has moved to its final position", "The list is reversed", "Every pair has been compared exactly twice"],
    "answer": 1,
    "explain": "Each pass 'bubbles' the biggest unsorted value all the way to the end of the unsorted portion."
  },
  {
    "q": "Why does the `swapped` flag matter?",
    "choices": ["It counts the total number of swaps", "It lets the sort stop early once a pass makes no swaps", "It reverses the comparison order", "It's required for correctness"],
    "answer": 1,
    "explain": "A pass with zero swaps means the list is already sorted - continuing would just waste more passes."
  },
  {
    "q": "Why is bubble sort O(n²) in the worst case?",
    "choices": ["It only works on n items or fewer", "It needs roughly n passes of roughly n comparisons each", "It compares every item to itself", "It uses recursion, which doubles the cost"],
    "answer": 1,
    "explain": "Worst case (reverse-sorted data), you need about n passes, each doing about n comparisons - n times n is n²."
  }
]
```


---

# Merge Sort (and Quick Sort)

Bubble sort's problem is that it only ever fixes one item's position per full walk through the data. Merge
sort takes a completely different strategy: **divide and conquer** - break the problem into pieces small
enough to be trivial, then combine the solved pieces back into a full answer.

## The mental model: split, solve, combine

**What it actually is.** A list of one item is already sorted - that's your base case (this is the same
shrink-toward-a-base-case shape as [recursion](/guides/recursion-finally-clicks)). Split any longer list into
two halves, recursively sort each half, then **merge** the two already-sorted halves into one sorted list by
repeatedly taking whichever half's front item is smaller.

```mermaid
flowchart TD
  A["[5,2,9,1,5,6]"] --> B["[5,2,9]"] & C["[1,5,6]"]
  B --> D["[5,2]"] & E["[9]"]
  C --> F["[1,5]"] & G["[6]"]
  D --> H["[5]"] & I["[2]"]
  F --> J["[1]"] & K["[5]"]
```
*Split all the way down to single items (already sorted by definition), then merge back up.*

```python runnable
def merge_sort(items):
    if len(items) <= 1:
        return items
    mid = len(items) // 2
    left = merge_sort(items[:mid])
    right = merge_sort(items[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])   # whichever side has leftovers, they're already sorted
    result.extend(right[j:])
    return result

print(merge_sort([5, 2, 9, 1, 5, 6]))
```
```console
[1, 2, 5, 5, 6, 9]
```
*What just happened:* `merge_sort` keeps splitting until it hits single items, then `merge` walks the two
sorted halves side by side, always taking the smaller front item - the same trick you'd use combining two
sorted piles of cards by hand. Because both halves are already sorted going in, `merge` never has to look
back once it's placed an item.

The split-solve-combine shape is the same in any language. Here is merge sort and its `merge` helper across
seven of them, each returning a fresh sorted list:

[[codegroup Merge Sort]]

```python
def merge_sort(items):
    if len(items) <= 1:
        return items
    mid = len(items) // 2
    return merge(merge_sort(items[:mid]), merge_sort(items[mid:]))

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result
```

```javascript
function mergeSort(items) {
  if (items.length <= 1) return items;
  const mid = Math.floor(items.length / 2);
  return merge(mergeSort(items.slice(0, mid)), mergeSort(items.slice(mid)));
}

function merge(left, right) {
  const result = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) result.push(left[i++]);
    else result.push(right[j++]);
  }
  return result.concat(left.slice(i), right.slice(j));
}
```

```typescript
function mergeSort(items: number[]): number[] {
  if (items.length <= 1) return items;
  const mid = Math.floor(items.length / 2);
  return merge(mergeSort(items.slice(0, mid)), mergeSort(items.slice(mid)));
}

function merge(left: number[], right: number[]): number[] {
  const result: number[] = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) result.push(left[i++]);
    else result.push(right[j++]);
  }
  return result.concat(left.slice(i), right.slice(j));
}
```

```java
static int[] mergeSort(int[] items) {
    if (items.length <= 1) return items;
    int mid = items.length / 2;
    int[] left = mergeSort(Arrays.copyOfRange(items, 0, mid));
    int[] right = mergeSort(Arrays.copyOfRange(items, mid, items.length));
    return merge(left, right);
}

static int[] merge(int[] left, int[] right) {
    int[] result = new int[left.length + right.length];
    int i = 0, j = 0, k = 0;
    while (i < left.length && j < right.length)
        result[k++] = (left[i] <= right[j]) ? left[i++] : right[j++];
    while (i < left.length) result[k++] = left[i++];
    while (j < right.length) result[k++] = right[j++];
    return result;
}
```

```cpp
std::vector<int> merge_sort(std::vector<int> items) {
    if (items.size() <= 1) return items;
    size_t mid = items.size() / 2;
    auto left = merge_sort({items.begin(), items.begin() + mid});
    auto right = merge_sort({items.begin() + mid, items.end()});
    std::vector<int> result;
    size_t i = 0, j = 0;
    while (i < left.size() && j < right.size())
        result.push_back(left[i] <= right[j] ? left[i++] : right[j++]);
    while (i < left.size()) result.push_back(left[i++]);
    while (j < right.size()) result.push_back(right[j++]);
    return result;
}
```

```go
func mergeSort(items []int) []int {
    if len(items) <= 1 {
        return items
    }
    mid := len(items) / 2
    left := mergeSort(items[:mid])
    right := mergeSort(items[mid:])
    result := make([]int, 0, len(items))
    i, j := 0, 0
    for i < len(left) && j < len(right) {
        if left[i] <= right[j] {
            result = append(result, left[i]); i++
        } else {
            result = append(result, right[j]); j++
        }
    }
    result = append(result, left[i:]...)
    result = append(result, right[j:]...)
    return result
}
```

```rust
fn merge_sort(items: &[i32]) -> Vec<i32> {
    if items.len() <= 1 {
        return items.to_vec();
    }
    let mid = items.len() / 2;
    let left = merge_sort(&items[..mid]);
    let right = merge_sort(&items[mid..]);
    let mut result = Vec::with_capacity(items.len());
    let (mut i, mut j) = (0, 0);
    while i < left.len() && j < right.len() {
        if left[i] <= right[j] {
            result.push(left[i]); i += 1;
        } else {
            result.push(right[j]); j += 1;
        }
    }
    result.extend_from_slice(&left[i..]);
    result.extend_from_slice(&right[j..]);
    result
}
```

[[/codegroup]]

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

**What it actually is.** Splitting the list in half repeatedly takes `log n` levels (the same halving as
binary search). At *each* level, merging back together touches every item once - `n` work per level. Multiply
them: `n` work × `log n` levels = `O(n log n)` total. That holds true in the **worst case, every time** -
merge sort's speed doesn't depend on how the input happened to be arranged.

💡 **Key point.** `O(n log n)` is the practical ceiling for general-purpose sorting - you can't reliably do
better by comparing items pairwise. It's what `sorted()` in Python and `.sort()` in JavaScript actually run
under the hood (with real-world tuning on top).

⚠️ **Gotcha: the memory cost.** `merge` builds a brand-new list instead of rearranging the original in
place. That's what gives merge sort its guaranteed `O(n log n)` - but it costs extra memory proportional to
`n`, which matters if you're sorting something huge with little RAM to spare.

## Quick sort: partition instead of merge

Quick sort is also divide and conquer, but it splits differently: pick a **pivot** value, then partition the
list into everything smaller than the pivot and everything bigger. Recursively sort each side, and there's
nothing left to merge - the pivot is already in its final position once both sides are sorted.

```python runnable
def quick_sort(items):
    if len(items) <= 1:
        return items
    pivot = items[len(items) // 2]
    less = [x for x in items if x < pivot]
    equal = [x for x in items if x == pivot]
    greater = [x for x in items if x > pivot]
    return quick_sort(less) + equal + quick_sort(greater)

print(quick_sort([5, 2, 9, 1, 5, 6]))
```
```console
[1, 2, 5, 5, 6, 9]
```
*What just happened:* everything less than the pivot goes left, everything greater goes right, and each side
recurses on its own. No merge step - once the two sides are sorted and stitched back around the pivot, the
whole thing is sorted.

**The trade-off.** With a well-chosen pivot, quick sort splits the data roughly in half each time - same
`O(n log n)` shape as merge sort, but sorting in place (no extra full-size copy). The catch: a *badly* chosen
pivot (say, always picking the first item on data that's already sorted) can split the list into "one item"
and "everything else" at every step, degrading to `O(n²)` - bubble sort's territory. Real-world quick sort
implementations pick the pivot more carefully (randomly, or the median of a few samples) specifically to make
that worst case rare.

| | Merge sort | Quick sort |
|---|---|---|
| Typical speed | `O(n log n)` | `O(n log n)` |
| Worst case | `O(n log n)` (guaranteed) | `O(n²)` (bad pivot) |
| Extra memory | Yes - a full copy | No - sorts in place |

Neither is "better" outright: merge sort trades memory for a guarantee, quick sort trades a rare worst case
for speed and low memory. Either one is what you're actually running any time you call a language's built-in
sort - bubble sort's `O(n²)` is the thing they were both invented to avoid.

```quiz
[
  {
    "q": "What is the base case in merge sort's recursion?",
    "choices": ["An empty list", "A list of one item - already sorted by definition", "A list of exactly two items", "There is no base case"],
    "answer": 1,
    "explain": "A single-item list can't be out of order, so it needs no further splitting - that's what stops the recursion."
  },
  {
    "q": "Why is merge sort O(n log n) instead of O(n²)?",
    "choices": ["It never compares two items", "It splits into log n levels, and each level does n work merging - n × log n total", "It skips half the data", "It only works on already-sorted input"],
    "answer": 1,
    "explain": "The halving gives log n levels; each level's merge step touches every item once, so total work is n times log n."
  },
  {
    "q": "What causes quick sort's worst-case O(n²) behavior?",
    "choices": ["Sorting a list that's already sorted, period", "A consistently badly-chosen pivot that splits the data very unevenly", "Using recursion instead of a loop", "Lists longer than 1000 items"],
    "answer": 1,
    "explain": "If the pivot is repeatedly the smallest or largest remaining value, each partition only removes one item instead of roughly halving the data."
  }
]
```