# Sorting Without a Second Copy: Quicksort

Sort 2 million photos by date on a phone that's short of memory: why merge sort's second copy and selection sort's trillions of comparisons both fall short, and the sort that does its work in place, quicksort, with the one bad day you have to guard against.

Journeyman · Data Structures · Updated November 17, 2026

By Gregor Dzierzon

## After this lesson you can

- Trace quicksort's partition around a pivot
- Explain why quicksort is usually O(n log n), and what makes its worst case O(n²)
- Choose between merge sort, quicksort and a simple sort for a sorting job, and say why

## Key takeaways

- Quicksort picks a pivot, splits the other items into those smaller than it and the rest, and sorts each side with quicksort.
- Splitting around the pivot is called partitioning; after it, the pivot is in its final place.
- When pivots land near the middle, quicksort is O(n log n), and in practice it's usually the fastest sort.
- When pivots keep landing at an end, as with the last item of an already sorted list, it slows to O(n²); a random pivot makes that bad day very unlikely.
- Partitioning by swapping inside the one list needs no second copy, only the call stack: O(log n) extra memory, where merge sort needs O(n).

**Before this:** *A Million Songs to Sort Before Bedtime: Merge Sort* (fast on any list, but every merge builds a new list: a second copy of everything).

A phone's photo gallery shows 2 million photos, newest first, and after a backup is restored they come back in no order. The gallery has to sort them by date, on the phone, while other apps are open and memory is short. Ask for too much and the phone closes the gallery.

## What would you try?

**Merge sort.** About 2,000,000 × 21 levels, some 42 million steps: fast. But every merge builds a new list, so it needs a second copy of the whole list. If each photo's entry (its date, its name and where it's stored) takes about 64 bytes, that's about 128 MB more, on a phone that hasn't got it. O(n) extra memory.

**Selection sort, in place.** It never copies: it swaps inside the one list, O(1) extra memory. But it compares every pair: 2,000,000 × 2,000,000 ÷ 2, about **2 trillion** comparisons. O(n²).

| What we tried | Time | Extra memory | Where it breaks |
|---|---|---|---|
| Merge sort | O(n log n), about 42 million steps | O(n), about 128 MB | the second copy |
| Selection sort | O(n²), about 2 trillion comparisons | O(1) | the time |

What we'd like is merge sort's speed with selection sort's memory.

## The questions that lead to it

**Where does merge sort do its work?** On the way back up, merging, and merging needs somewhere to put the result. Could the work happen on the way **down**, so nothing needs merging at all?

**Pick one photo, say one from June 2021, and make two piles: everything taken before it, and everything after.** Where does that photo end up in the finished gallery? Exactly between the piles. It's already in its final place, and it will never move again.

**Then sort each pile the same way.** Once both piles are sorted, before-pile, the June photo, after-pile is the whole gallery in order. Nothing to merge. And if the piles can be made by swapping photos inside the one list, there's no second copy either.

## How it got its name

This idea was so useful that it got a name: **quicksort**, a name it usually lives up to. You may already sort this way without being taught: grab one graded test, say a 70, put everything below 70 on the left and everything else on the right, then do the same with each pile.

- **Pick a pivot.** In this lesson it's the last item of the list.
- **Partition:** put every other item into one of two piles, the ones smaller than the pivot and the rest. The pivot goes between them, and that's its final place: everything on its left is smaller and everything on its right isn't.
- **Sort each pile** with quicksort. A pile of one item, or none, is already sorted.
- There's nothing to merge: smaller pile, pivot, other pile is already in order.

It's divide and conquer, like merge sort, but it does its work on the way down instead of on the way back up.

## Quicksort in code

Here are the eight cards from *A Million Songs to Sort Before Bedtime: Merge Sort*, sorted with quicksort, printing every partition. To keep the piles easy to see, this version builds them as new lists; the next section shows how the real one makes them without any, and its code:

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

List<int> QuickSort(List<int> cards)
{
    if (cards.Count <= 1)
    {
        return cards;
    }
    int pivot = cards[cards.Count - 1];
    List<int> smaller = new List<int>();
    List<int> rest = new List<int>();
    for (int i = 0; i < cards.Count - 1; i++)
    {
        if (cards[i] < pivot)
        {
            smaller.Add(cards[i]);
        }
        else
        {
            rest.Add(cards[i]);
        }
    }
    Console.WriteLine("Pivot " + pivot + ": " + Show(smaller) + " " + pivot + " " + Show(rest));

    List<int> sorted = QuickSort(smaller);
    sorted.Add(pivot);
    sorted.AddRange(QuickSort(rest));
    return sorted;
}

Console.WriteLine("Sorted: " + Show(QuickSort(new List<int> { 8, 3, 5, 1, 7, 2, 6, 4 })));
```

```text
Pivot 4: [3, 1, 2] 4 [8, 5, 7, 6]
Pivot 2: [1] 2 [3]
Pivot 6: [5] 6 [8, 7]
Pivot 7: [] 7 [8]
Sorted: [1, 2, 3, 4, 5, 6, 7, 8]
```

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

List<Integer> quickSort(List<Integer> cards) {
    if (cards.size() <= 1) {
        return cards;
    }
    int pivot = cards.get(cards.size() - 1);
    List<Integer> smaller = new ArrayList<>();
    List<Integer> rest = new ArrayList<>();
    for (int i = 0; i < cards.size() - 1; i++) {
        if (cards.get(i) < pivot) {
            smaller.add(cards.get(i));
        } else {
            rest.add(cards.get(i));
        }
    }
    IO.println("Pivot " + pivot + ": " + show(smaller) + " " + pivot + " " + show(rest));

    List<Integer> sorted = new ArrayList<>(quickSort(smaller));
    sorted.add(pivot);
    sorted.addAll(quickSort(rest));
    return sorted;
}

void main() {
    IO.println("Sorted: " + show(quickSort(List.of(8, 3, 5, 1, 7, 2, 6, 4))));
}
```

```text
Pivot 4: [3, 1, 2] 4 [8, 5, 7, 6]
Pivot 2: [1] 2 [3]
Pivot 6: [5] 6 [8, 7]
Pivot 7: [] 7 [8]
Sorted: [1, 2, 3, 4, 5, 6, 7, 8]
```

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


def quick_sort(cards):
    if len(cards) <= 1:
        return cards
    pivot = cards[-1]
    smaller = []
    rest = []
    for card in cards[:-1]:
        if card < pivot:
            smaller.append(card)
        else:
            rest.append(card)
    print(f"Pivot {pivot}: {show(smaller)} {pivot} {show(rest)}")

    return quick_sort(smaller) + [pivot] + quick_sort(rest)


print(f"Sorted: {show(quick_sort([8, 3, 5, 1, 7, 2, 6, 4]))}")
```

```text
Pivot 4: [3, 1, 2] 4 [8, 5, 7, 6]
Pivot 2: [1] 2 [3]
Pivot 6: [5] 6 [8, 7]
Pivot 7: [] 7 [8]
Sorted: [1, 2, 3, 4, 5, 6, 7, 8]
```

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

function quickSort(cards) {
  if (cards.length <= 1) {
    return cards;
  }
  const pivot = cards[cards.length - 1];
  const smaller = [];
  const rest = [];
  for (const card of cards.slice(0, -1)) {
    if (card < pivot) {
      smaller.push(card);
    } else {
      rest.push(card);
    }
  }
  console.log(`Pivot ${pivot}: ${show(smaller)} ${pivot} ${show(rest)}`);

  return [...quickSort(smaller), pivot, ...quickSort(rest)];
}

console.log(`Sorted: ${show(quickSort([8, 3, 5, 1, 7, 2, 6, 4]))}`);
```

```text
Pivot 4: [3, 1, 2] 4 [8, 5, 7, 6]
Pivot 2: [1] 2 [3]
Pivot 6: [5] 6 [8, 7]
Pivot 7: [] 7 [8]
Sorted: [1, 2, 3, 4, 5, 6, 7, 8]
```

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

function quickSort(cards: number[]): number[] {
  if (cards.length <= 1) {
    return cards;
  }
  const pivot = cards[cards.length - 1]!;
  const smaller: number[] = [];
  const rest: number[] = [];
  for (const card of cards.slice(0, -1)) {
    if (card < pivot) {
      smaller.push(card);
    } else {
      rest.push(card);
    }
  }
  console.log(`Pivot ${pivot}: ${show(smaller)} ${pivot} ${show(rest)}`);

  return [...quickSort(smaller), pivot, ...quickSort(rest)];
}

console.log(`Sorted: ${show(quickSort([8, 3, 5, 1, 7, 2, 6, 4]))}`);
```

```text
Pivot 4: [3, 1, 2] 4 [8, 5, 7, 6]
Pivot 2: [1] 2 [3]
Pivot 6: [5] 6 [8, 7]
Pivot 7: [] 7 [8]
Sorted: [1, 2, 3, 4, 5, 6, 7, 8]
```

Read the first line: after one partition, 4 is in its final place, with 3, 1 and 2 on its left and 8, 5, 7 and 6 on its right. Each side is then sorted on its own, and the piles of one card (`[1]`, `[3]`, `[5]`, `[8]`) print nothing because they're already sorted.

![The eight cards 8, 3, 5, 1, 7, 2, 6, 4 partitioned step by step: pivot 4 splits them into 3, 1, 2 on the left and 8, 5, 7, 6 on the right; pivot 2 splits the left into 1 and 3; pivot 6 splits the right into 5 and 8, 7; pivot 7 places 8 after it; each pivot is outlined and stays fixed in its final place, until the row reads 1 to 8](https://fsdtrainingmedia.blob.core.windows.net/public/images/2026/11/f6616478c8d04d90ad7b4d98564517be.webp)

## Partitioning in place: no second copy

The code above built new piles so you could see them, and that would put the second copy right back. The quicksort inside real libraries partitions **in place**: it makes the two piles by swapping items within the one list. Here's the first partition of the same eight cards, done that way. A boundary marks the end of the "smaller than 4" part, and it starts empty, before the first card:

- 8 isn't smaller than 4: it stays.
- 3 is smaller: swap it with the first card after the boundary, the 8. Now 3 8 5 1 7 2 6 4, and the boundary moves past the 3.
- 5 isn't smaller. 1 is: swap it with the 8. Now 3 1 5 8 7 2 6 4.
- 7 isn't smaller. 2 is: swap it with the 5. Now 3 1 2 8 7 5 6 4.
- 6 isn't smaller. Last, swap the pivot with the first card after the boundary, the 8: **3 1 2 4 7 5 6 8**.

Four swaps, no second list, and 4 is in its final place with 3, 1 and 2 on its left. The right pile holds the same cards as the piles version's, in another order (7 5 6 8 instead of 8 5 7 6), which doesn't matter: it gets sorted next.

Here's quicksort with that partition. `partition` works on one stretch of the list, from position `low` to position `high`: it swaps the cards smaller than the stretch's last card to its front, puts that pivot right after them, and says where the pivot landed. Quicksort then sorts the stretch on each side of the pivot, in the same list. It prints the whole list after every partition:

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

void Swap(int[] cards, int a, int b)
{
    int held = cards[a];
    cards[a] = cards[b];
    cards[b] = held;
}

int Partition(int[] cards, int low, int high)
{
    int pivot = cards[high];
    int boundary = low;
    for (int i = low; i < high; i++)
    {
        if (cards[i] < pivot)
        {
            Swap(cards, i, boundary);
            boundary++;
        }
    }
    Swap(cards, high, boundary);
    return boundary;
}

void QuickSort(int[] cards, int low, int high)
{
    if (low >= high)
    {
        return;
    }
    int place = Partition(cards, low, high);
    Console.WriteLine("Pivot " + cards[place] + ": " + Show(cards));
    QuickSort(cards, low, place - 1);
    QuickSort(cards, place + 1, high);
}

int[] hand = { 8, 3, 5, 1, 7, 2, 6, 4 };
QuickSort(hand, 0, hand.Length - 1);
Console.WriteLine("Sorted: " + Show(hand));
```

```text
Pivot 4: [3, 1, 2, 4, 7, 5, 6, 8]
Pivot 2: [1, 2, 3, 4, 7, 5, 6, 8]
Pivot 8: [1, 2, 3, 4, 7, 5, 6, 8]
Pivot 6: [1, 2, 3, 4, 5, 6, 7, 8]
Sorted: [1, 2, 3, 4, 5, 6, 7, 8]
```

```java
String show(int[] cards) {
    return Arrays.toString(cards);
}

void swap(int[] cards, int a, int b) {
    int held = cards[a];
    cards[a] = cards[b];
    cards[b] = held;
}

int partition(int[] cards, int low, int high) {
    int pivot = cards[high];
    int boundary = low;
    for (int i = low; i < high; i++) {
        if (cards[i] < pivot) {
            swap(cards, i, boundary);
            boundary++;
        }
    }
    swap(cards, high, boundary);
    return boundary;
}

void quickSort(int[] cards, int low, int high) {
    if (low >= high) {
        return;
    }
    int place = partition(cards, low, high);
    IO.println("Pivot " + cards[place] + ": " + show(cards));
    quickSort(cards, low, place - 1);
    quickSort(cards, place + 1, high);
}

void main() {
    int[] hand = {8, 3, 5, 1, 7, 2, 6, 4};
    quickSort(hand, 0, hand.length - 1);
    IO.println("Sorted: " + show(hand));
}
```

```text
Pivot 4: [3, 1, 2, 4, 7, 5, 6, 8]
Pivot 2: [1, 2, 3, 4, 7, 5, 6, 8]
Pivot 8: [1, 2, 3, 4, 7, 5, 6, 8]
Pivot 6: [1, 2, 3, 4, 5, 6, 7, 8]
Sorted: [1, 2, 3, 4, 5, 6, 7, 8]
```

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


def partition(cards, low, high):
    pivot = cards[high]
    boundary = low
    for i in range(low, high):
        if cards[i] < pivot:
            cards[i], cards[boundary] = cards[boundary], cards[i]
            boundary += 1
    cards[high], cards[boundary] = cards[boundary], cards[high]
    return boundary


def quick_sort(cards, low, high):
    if low >= high:
        return
    place = partition(cards, low, high)
    print(f"Pivot {cards[place]}: {show(cards)}")
    quick_sort(cards, low, place - 1)
    quick_sort(cards, place + 1, high)


hand = [8, 3, 5, 1, 7, 2, 6, 4]
quick_sort(hand, 0, len(hand) - 1)
print(f"Sorted: {show(hand)}")
```

```text
Pivot 4: [3, 1, 2, 4, 7, 5, 6, 8]
Pivot 2: [1, 2, 3, 4, 7, 5, 6, 8]
Pivot 8: [1, 2, 3, 4, 7, 5, 6, 8]
Pivot 6: [1, 2, 3, 4, 5, 6, 7, 8]
Sorted: [1, 2, 3, 4, 5, 6, 7, 8]
```

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

function swap(cards, a, b) {
  const held = cards[a];
  cards[a] = cards[b];
  cards[b] = held;
}

function partition(cards, low, high) {
  const pivot = cards[high];
  let boundary = low;
  for (let i = low; i < high; i++) {
    if (cards[i] < pivot) {
      swap(cards, i, boundary);
      boundary++;
    }
  }
  swap(cards, high, boundary);
  return boundary;
}

function quickSort(cards, low, high) {
  if (low >= high) {
    return;
  }
  const place = partition(cards, low, high);
  console.log(`Pivot ${cards[place]}: ${show(cards)}`);
  quickSort(cards, low, place - 1);
  quickSort(cards, place + 1, high);
}

const hand = [8, 3, 5, 1, 7, 2, 6, 4];
quickSort(hand, 0, hand.length - 1);
console.log(`Sorted: ${show(hand)}`);
```

```text
Pivot 4: [3, 1, 2, 4, 7, 5, 6, 8]
Pivot 2: [1, 2, 3, 4, 7, 5, 6, 8]
Pivot 8: [1, 2, 3, 4, 7, 5, 6, 8]
Pivot 6: [1, 2, 3, 4, 5, 6, 7, 8]
Sorted: [1, 2, 3, 4, 5, 6, 7, 8]
```

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

function swap(cards: number[], a: number, b: number): void {
  const held = cards[a]!;
  cards[a] = cards[b]!;
  cards[b] = held;
}

function partition(cards: number[], low: number, high: number): number {
  const pivot = cards[high]!;
  let boundary = low;
  for (let i = low; i < high; i++) {
    if (cards[i]! < pivot) {
      swap(cards, i, boundary);
      boundary++;
    }
  }
  swap(cards, high, boundary);
  return boundary;
}

function quickSort(cards: number[], low: number, high: number): void {
  if (low >= high) {
    return;
  }
  const place = partition(cards, low, high);
  console.log(`Pivot ${cards[place]}: ${show(cards)}`);
  quickSort(cards, low, place - 1);
  quickSort(cards, place + 1, high);
}

const hand: number[] = [8, 3, 5, 1, 7, 2, 6, 4];
quickSort(hand, 0, hand.length - 1);
console.log(`Sorted: ${show(hand)}`);
```

```text
Pivot 4: [3, 1, 2, 4, 7, 5, 6, 8]
Pivot 2: [1, 2, 3, 4, 7, 5, 6, 8]
Pivot 8: [1, 2, 3, 4, 7, 5, 6, 8]
Pivot 6: [1, 2, 3, 4, 5, 6, 7, 8]
Sorted: [1, 2, 3, 4, 5, 6, 7, 8]
```

The first line is the four swaps above: 3 1 2 4 7 5 6 8. Every line is the same eight cards in the same one list, a little more in order each time. Pivot 2 sorts the left pile, 3 1 2, into 1 2 3. The right pile is 7 5 6 8 here, so its pivot is 8, the largest: every card is smaller, each one "swaps" with itself, and nothing moves. Then pivot 6 sorts 7 5 6 into 5 6 7.

Nothing was copied. The only extra memory is the call stack, one frame per level of piles: O(log n) when the piles halve. For the 2 million photos that's about 21 frames instead of a 128 MB copy.

## Its good days and its bad day

When the pivot lands near the middle, each partition halves the problem, like merge sort: about log n levels, each touching all n items, so **O(n log n)**. On real, jumbled data that's what happens, and quicksort's small, tight loop usually makes it the fastest sort in practice.

Now feed it a list that's **already sorted**, which is easy to do by accident (a gallery that was sorted yesterday) or on purpose (someone who wants your server to slow down can send it sorted data). The last item is the largest, so every partition puts everything into the smaller pile and nothing into the other. Each level removes only one item, the pivot: n levels instead of log n. This code counts the comparisons with the pivot for 500 items, shuffled and already sorted:

```csharp
int comparisons = 0;

List<int> QuickSort(List<int> cards)
{
    if (cards.Count <= 1)
    {
        return cards;
    }
    int pivot = cards[cards.Count - 1];
    comparisons += cards.Count - 1;
    List<int> smaller = new List<int>();
    List<int> rest = new List<int>();
    for (int i = 0; i < cards.Count - 1; i++)
    {
        if (cards[i] < pivot)
        {
            smaller.Add(cards[i]);
        }
        else
        {
            rest.Add(cards[i]);
        }
    }
    List<int> sorted = QuickSort(smaller);
    sorted.Add(pivot);
    sorted.AddRange(QuickSort(rest));
    return sorted;
}

List<int> shuffled = new List<int>();
List<int> inOrder = new List<int>();
for (int i = 0; i < 500; i++)
{
    shuffled.Add(i * 7919 % 500);
    inOrder.Add(i);
}
QuickSort(shuffled);
Console.WriteLine("Shuffled: " + comparisons + " comparisons");
comparisons = 0;
QuickSort(inOrder);
Console.WriteLine("Already sorted: " + comparisons + " comparisons");
```

```text
Shuffled: 4493 comparisons
Already sorted: 124750 comparisons
```

```java
int comparisons = 0;

List<Integer> quickSort(List<Integer> cards) {
    if (cards.size() <= 1) {
        return cards;
    }
    int pivot = cards.get(cards.size() - 1);
    comparisons += cards.size() - 1;
    List<Integer> smaller = new ArrayList<>();
    List<Integer> rest = new ArrayList<>();
    for (int i = 0; i < cards.size() - 1; i++) {
        if (cards.get(i) < pivot) {
            smaller.add(cards.get(i));
        } else {
            rest.add(cards.get(i));
        }
    }
    List<Integer> sorted = new ArrayList<>(quickSort(smaller));
    sorted.add(pivot);
    sorted.addAll(quickSort(rest));
    return sorted;
}

void main() {
    List<Integer> shuffled = new ArrayList<>();
    List<Integer> inOrder = new ArrayList<>();
    for (int i = 0; i < 500; i++) {
        shuffled.add(i * 7919 % 500);
        inOrder.add(i);
    }
    quickSort(shuffled);
    IO.println("Shuffled: " + comparisons + " comparisons");
    comparisons = 0;
    quickSort(inOrder);
    IO.println("Already sorted: " + comparisons + " comparisons");
}
```

```text
Shuffled: 4493 comparisons
Already sorted: 124750 comparisons
```

```python
comparisons = 0


def quick_sort(cards):
    global comparisons
    if len(cards) <= 1:
        return cards
    pivot = cards[-1]
    comparisons += len(cards) - 1
    smaller = [card for card in cards[:-1] if card < pivot]
    rest = [card for card in cards[:-1] if card >= pivot]
    return quick_sort(smaller) + [pivot] + quick_sort(rest)


shuffled = [i * 7919 % 500 for i in range(500)]
in_order = list(range(500))
quick_sort(shuffled)
print(f"Shuffled: {comparisons} comparisons")
comparisons = 0
quick_sort(in_order)
print(f"Already sorted: {comparisons} comparisons")
```

```text
Shuffled: 4493 comparisons
Already sorted: 124750 comparisons
```

```javascript
let comparisons = 0;

function quickSort(cards) {
  if (cards.length <= 1) {
    return cards;
  }
  const pivot = cards[cards.length - 1];
  comparisons += cards.length - 1;
  const smaller = cards.slice(0, -1).filter((card) => card < pivot);
  const rest = cards.slice(0, -1).filter((card) => card >= pivot);
  return [...quickSort(smaller), pivot, ...quickSort(rest)];
}

const shuffled = [];
const inOrder = [];
for (let i = 0; i < 500; i++) {
  shuffled.push(i * 7919 % 500);
  inOrder.push(i);
}
quickSort(shuffled);
console.log(`Shuffled: ${comparisons} comparisons`);
comparisons = 0;
quickSort(inOrder);
console.log(`Already sorted: ${comparisons} comparisons`);
```

```text
Shuffled: 4493 comparisons
Already sorted: 124750 comparisons
```

```typescript
let comparisons = 0;

function quickSort(cards: number[]): number[] {
  if (cards.length <= 1) {
    return cards;
  }
  const pivot = cards[cards.length - 1]!;
  comparisons += cards.length - 1;
  const smaller = cards.slice(0, -1).filter((card) => card < pivot);
  const rest = cards.slice(0, -1).filter((card) => card >= pivot);
  return [...quickSort(smaller), pivot, ...quickSort(rest)];
}

const shuffled: number[] = [];
const inOrder: number[] = [];
for (let i = 0; i < 500; i++) {
  shuffled.push(i * 7919 % 500);
  inOrder.push(i);
}
quickSort(shuffled);
console.log(`Shuffled: ${comparisons} comparisons`);
comparisons = 0;
quickSort(inOrder);
console.log(`Already sorted: ${comparisons} comparisons`);
```

```text
Shuffled: 4493 comparisons
Already sorted: 124750 comparisons
```

`i * 7919 % 500` mixes up the numbers 0 to 499 in a fixed order, so every language gets the same "shuffled" list and the same count. Already sorted, the same 500 items take 124,750 comparisons, the full 499 + 498 + … + 1 of *Putting the Leaderboard in Order: Selection Sort*: **O(n²)**, nearly 28 times the work. It also recurses 500 levels deep, and a big enough sorted list would overflow the call stack.

The fix is a better pivot. Real quicksorts pick a **random** item, or the middle value of the first, middle and last items (**median of three**). Then a sorted list is no longer a trap, and the bad day needs bad luck on almost every pick, which practically never happens. C#'s built-in sort goes further: if the recursion gets too deep, it switches to a sort with no bad day.

**Try it.** Change the pivot to the middle item of the list (`cards[cards.Count / 2]` in C#, `cards[len(cards) // 2]` in Python, `cards[Math.floor(cards.length / 2)]` in JavaScript), skip that item instead of the last when making the piles, and count the already-sorted list's comparisons again.

## Choosing between the fast sorts

- **Memory is short:** quicksort, in place.
- **The worst case must never happen,** or ties must keep their order: merge sort. It has no bad day, and it's stable (more on that in *Most Played, Then A to Z: Stable and Built-In Sorts*), which an in-place quicksort isn't.
- **The list is almost sorted, or short:** insertion sort.
- **In real code:** your language's built-in sort, which mixes these for you.

## The cost card

| Operation | Big-O | The everyday reason |
|---|---|---|
| Sort, best and average case | O(n log n) | pivots land near the middle, so each partition halves the pile |
| Sort, worst case | O(n²) | the pivot lands at an end every time, so each partition removes one item |
| Partition around one pivot | O(n) | every item is compared with the pivot once |
| Extra memory, in place | O(log n) | the call stack's frames, one per level, when the piles are halved |

## Check yourself

2 questions to try on the lesson page.

## So what

Quicksort is the sort most built-in libraries reach for first: on real data it's the fastest, and it needs no second copy. Remember its one weakness: a predictable pivot on already sorted data turns O(n log n) into O(n²), which is why real pivots are random or picked from three.

## Key terms

- [Quicksort](https://www.ask-codey.com/glossary/quicksort)
- [Pivot](https://www.ask-codey.com/glossary/pivot)
- [Divide and Conquer](https://www.ask-codey.com/glossary/divide-and-conquer)
- [Worst Case](https://www.ask-codey.com/glossary/worst-case)

## Cheat sheets

- [Sorting Without a Second Copy: Quicksort](https://www.ask-codey.com/cheat-sheets/ds-quicksort-cheat-sheet)

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