Skip to content

Sorting

Lesson 7 of 7 in Core Patterns · 45 min · Intermediate

Put things in order, then problems get easier.

Introduction

You sort ten playing cards by picking each one up and sliding it into place in your hand. Why would that same method be hopeless for a million exam scores?

With ten cards, each new card passes about half of the cards already in your hand. The whole job is a few dozen moves, and you barely notice.

Now try the same slide-it-into-place method on a million scores. It needs about n × n ÷ 4 moves, which is roughly 250 billion. Even at a billion moves a second, that is over four minutes for a single sort.

Lesson overview

This lesson will show you how to:

  • Explain why insertion sort slows to about n squared moves on large inputs.
  • Trace merge sort as it halves the range, then merges sorted piles.
  • Trace quick sort's partition, placing the pivot in its final slot.
  • Compare insertion, merge and quick sort costs on a million items.
  • Explain why a stable sort keeps equal items in their original order.
  • Choose insertion sort for small or nearly sorted inputs.

The picture

nums20417293435jkey = 5sorted handkey held asidenot placed yetArray nums with 6 slots: 2, 4, 7, 9, empty, 3. Pointers: j at index 3. Window from index 0 to 4. Marked: index 3 compare; index 4 focus. Notes: key = 5.

Mental model

Sorting a hand of cards: you pick up one card at a time and slide it left past every bigger card until it fits. That is insertion sort. It is great when the hand is small or nearly in order.

Now picture two stacks of exam papers, each already sorted by score. To merge them you only ever compare the top paper of each stack: the lower score goes onto the new pile, and you repeat. Merge sort keeps halving a big stack until every pile is one paper, then merges the piles back up.

Quick sort splits by a different rule. Pick one paper as the pivot, put lower scores on its left and higher ones on its right. The pivot is now in its final spot, and each side is a smaller pile to sort the same way.

Sorting gets cheaper when you split the job: two small sorted piles merge in a single pass, so halving beats comparing everything with everything.

Words to know

stable
Equal items keep their original order. If two exam papers both score 80, the one that came first still comes first after sorting.
in-place
The sort rearranges the array itself and needs only a few extra variables, not a second array. Insertion sort and quick sort are in-place; merge sort needs a buffer.
comparison sort
A sort that learns the order only by asking "is a smaller than b?". Insertion, merge and quick sort are all comparison sorts.
pivot
The number quick sort picks to split a range: smaller numbers go on its left and the rest on its right. Here it is the last number of the range.
partition
Rearranging a range around the pivot so everything smaller is on the left and everything else is on the right. The pivot lands in its final slot.
divide and conquer
Split a problem into smaller copies of itself, solve each copy, then combine the answers. Merge sort and quick sort both work this way.
O(n log n) lower bound
No comparison sort can beat about n × log₂ n comparisons in the worst case. There are n! possible orders and each comparison can at most halve them.

Watch it run

Step with → or Next. When a question pops up, make your guess. Try your own input once the guided run ends.

Getting the demo ready…

Recognise it

Most of the skill is noticing the clue in the problem statement.

Reach for it when

  • Yes: The statement says sorted, order, rank, smallest first, or asks you to arrange or merge things by some rule.
  • Yes: Related items need to sit side by side: overlapping intervals, duplicates, or the closest pair.
  • Yes: You will search the same data many times, so sorting once lets binary search or two pointers do the rest.
  • Yes: A custom order is the whole trick, like ordering by end time or by which of a+b and b+a is bigger.

Not this when

  • No: You only need the largest, smallest or top k. One pass or a heap does less work than ordering everything.
  • No: The values live in a tiny known range, like 0, 1 and 2 or the letters a to z. Counting beats a comparison sort and runs in O(n).
  • No: You need one lookup in unsorted data. A hash map answers it in O(n) total, and sorting first would cost O(n log n) and scramble the original indexes.

Which pattern fits?

  1. Which pattern? 1 of 5

    Given an array of intervals [start, end], merge every pair that overlaps and return the merged list.

  2. Which pattern? 2 of 5

    Return the k-th largest element of an unsorted array. You don't need any other element in order.

  3. Which pattern? 3 of 5

    Given a list of non-negative integers, arrange them to form the largest possible number. For [3, 30, 34, 5, 9] the answer is "9534330".

  4. Which pattern? 4 of 5

    Given an unsorted array and a target, return the indices of two numbers that add up to the target.

  5. Which pattern? 5 of 5

    You have meetings with start and end times and one room. Attend as many meetings as possible without any overlap.

The code

First the idea in plain steps. Then the same idea as real code, line for line.

Pseudocode
  1. 1merged = a buffer as long as nums, then sort_range(0, n − 1)
  2. sort_range(lo, hi):
  3. 2if lo >= hi: return (one number is already sorted)
  4. 3mid = (lo + hi) / 2
  5. 3sort_range(lo, mid), then sort_range(mid + 1, hi)
  6. 4i = lo, j = mid + 1, k = lo
  7. while both halves still have numbers:
  8. 5put the smaller of nums[i] and nums[j] into merged[k]; ties go left
  9. 5move that pointer and k forward
  10. 6copy whatever is left of the half that remains
  11. 7copy merged[lo .. hi] back into nums
  12. 8return nums

The faint numbers are the rules in the Rule Rail under the stage. Same numbers, same order.

Getting the replay ready…

def merge_sort(nums):
    merged = [0] * len(nums)
    sort_range(nums, merged, 0, len(nums) - 1)
    return nums


def sort_range(nums, merged, lo, hi):
    if lo >= hi:
        return
    mid = (lo + hi) // 2
    sort_range(nums, merged, lo, mid)
    sort_range(nums, merged, mid + 1, hi)
    i, j, k = lo, mid + 1, lo
    while i <= mid and j <= hi:
        if nums[i] <= nums[j]:
            merged[k] = nums[i]
            i += 1
        else:
            merged[k] = nums[j]
            j += 1
        k += 1
    while i <= mid:
        merged[k] = nums[i]
        i += 1
        k += 1
    while j <= hi:
        merged[k] = nums[j]
        j += 1
        k += 1
    for p in range(lo, hi + 1):
        nums[p] = merged[p]
Time · O(n log n)Space · O(n)
  • Merge sort takes O(n log n) in the best, average and worst case. It is stable, and not in-place: the buffer costs O(n) extra space. Halving gives about log₂ n levels, and every level merges n numbers.
  • Insertion sort is O(n) when the input is already sorted and O(n²) on average and in the worst case. It is stable and in-place, uses O(1) extra space, and is hard to beat on tiny or nearly sorted inputs.
  • Quick sort is O(n log n) on average and O(n²) in the worst case. It is in-place but not stable, and its recursion uses O(log n) stack space on average.
  • The worst case for quick sort is easy to hit with a last-element pivot: on an already sorted array the pivot is always the biggest number, so each round peels off just one number (n + (n − 1) + ... + 1 comparisons).
  • Picking the pivot at random, or the median of the first, middle and last numbers, makes that bad case a matter of bad luck instead of bad input. The expected time becomes O(n log n) for every input.
  • No comparison sort can beat O(n log n) in the worst case. n numbers can be ordered n! ways and each comparison at most halves the possibilities, so you need about log₂(n!) ≈ n log₂ n comparisons.
  • In real code, just call the language's sort. Python: nums.sort() or sorted(items, key=lambda p: p[1]). Use key=, because Python 3's sort has no positional comparator; functools.cmp_to_key wraps an old-style one. Its sort is stable.
  • Java: Arrays.sort(nums) for an int[], and Arrays.sort(items, Comparator.comparingInt(p -> p[1])) or (a, b) -> Integer.compare(a[0], b[0]) for objects and rows. Avoid a[0] - b[0], which can overflow.
  • C++: std::sort(v.begin(), v.end()) for numbers, and std::sort(v.begin(), v.end(), [](const auto& a, const auto& b) { return a[1] < b[1]; }) with a lambda. std::sort is not guaranteed stable; use std::stable_sort when equal items must keep their order.
  • Write a sort yourself only when asked to, or when sorting is not the point: quick sort's partition powers k-th largest, and merge sort's merge step powers counting inversions.

Worked examples

Real interview problems, solved with the same recipe.

Open on LeetCode (opens in a new tab)

Given an array of integers nums, sort it in ascending order and return it. Solve it without using any built-in sorting function, in O(n log n) time.

Input

nums = [5,2,3,1]

Output

[1,2,3,5]

Approach

  1. Split [5, 2, 3, 1] into [5, 2] and [3, 1], then into single numbers. A single number is already sorted.
  2. Merge [5] with [2]: 2 is smaller, so you get [2, 5]. Merge [3] with [1] to get [1, 3].
  3. Merge [2, 5] with [1, 3]: take 1 (it beats 2), then 2 (it beats 3), then 3 (it beats 5), then copy the leftover 5. The result is [1, 2, 3, 5].
  4. There are about log₂ n levels of merging and each level handles n numbers, so the time is O(n log n) in every case. The buffer costs O(n) space.
def merge_sort(nums):
    merged = [0] * len(nums)
    sort_range(nums, merged, 0, len(nums) - 1)
    return nums


def sort_range(nums, merged, lo, hi):
    if lo >= hi:
        return
    mid = (lo + hi) // 2
    sort_range(nums, merged, lo, mid)
    sort_range(nums, merged, mid + 1, hi)
    i, j, k = lo, mid + 1, lo
    while i <= mid and j <= hi:
        if nums[i] <= nums[j]:
            merged[k] = nums[i]
            i += 1
        else:
            merged[k] = nums[j]
            j += 1
        k += 1
    while i <= mid:
        merged[k] = nums[i]
        i += 1
        k += 1
    while j <= hi:
        merged[k] = nums[j]
        j += 1
        k += 1
    for p in range(lo, hi + 1):
        nums[p] = merged[p]
Time · O(n log n)Space · O(n)

Knowledge check

Test yourself first. Try to answer these in your own words, then take the quiz below to check.

  1. About how many moves does insertion sort need, on average, to sort 1,000,000 shuffled numbers?
  2. Which cost does merge sort pay that quick sort mostly avoids?
  3. Quick sort always uses the last number as the pivot, and you give it an array that is already sorted. What happens?
  4. Why can't any sort that works by comparing pairs beat O(n log n) in the worst case?
  5. You sort people by age, then run a stable sort by city. Two people live in the same city. Who comes first?

Question 1 of 5

About how many moves does insertion sort need, on average, to sort 1,000,000 shuffled numbers?

Assignment

Pick one, try it cold for ten minutes, then come back for the hint.

0 of 8 solved

  1. Solve Merge Sorted Array (opens in a new tab) (LeetCode, easy)

    Hint: Fill nums1 from the back: the bigger of the two last numbers goes into the last free slot, so nothing you still need gets overwritten.

  2. Solve Valid Anagram (opens in a new tab) (LeetCode, easy)

    Hint: Two anagrams sort to the same string, so sort both and compare. Then ask whether counting the letters gets you there faster.

  3. Solve Largest Number (opens in a new tab) (LeetCode, medium)

    Hint: Don't sort by value. Sort by which of a + b and b + a, glued as strings, makes the bigger number.

  4. Solve Top K Frequent Elements (opens in a new tab) (LeetCode, medium)

    Hint: Count first, then order by count. You don't need a full sort: group numbers by frequency, or keep only k of them in a heap.

  5. Solve Kth Largest Element in an Array (opens in a new tab) (LeetCode, medium)

    Hint: A quick sort partition puts the pivot at its final index. If that index is the one you want you are done; otherwise only one side is left to explore.

  6. Solve Sort List (opens in a new tab) (LeetCode, medium)

    Hint: A linked list can't be indexed, so merge sort fits: find the middle with slow and fast pointers, sort each half, then merge the lists.

  7. Solve Non-overlapping Intervals (opens in a new tab) (LeetCode, medium)

    Hint: Sort by end time, keep every interval that starts at or after the last kept end, and count the ones you have to drop.

  8. Solve Count of Smaller Numbers After Self (opens in a new tab) (LeetCode, hard)

    Hint: The merge step already compares the left half with the right half. Sort indices instead of values, and count the right-half numbers that jump ahead of each left-half number.

Additional resources