Get started

Merge Sort Coding Problems: 2 Questions with Solutions

2 merge sort coding problems — 2 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 2-day plan.

  • Problems: 2
  • By difficulty: 2 hard
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
  • Cost: Free on every plan; sign in to run and submit

Merge sort splits an array in half, sorts each half recursively and merges the two sorted halves in one linear pass, for O(n log n) on every input and a stable result. In interviews the merge step matters as much for what it can count as for the sorting: while two sorted halves meet, every element can see how many on the other side are smaller or larger. The problems here use that to count pairs across positions in O(n log n) where comparing every pair would be O(n²).

How merge sort works, step by step

38274339821019
Sorting an array, with merge sort. Example: nums = [38, 27, 43, 3, 9, 82, 10, 19]
  1. Merge sort halves the array until every piece holds one number, then merges the pieces back together in order. One number on its own is already sorted, which is what the merging builds on.
  2. Split into two halves of 4: [38, 27, 43, 3] and [9, 82, 10, 19]. Splitting compares nothing; it only decides which pieces get merged later.
  3. Split each half again: [38, 27], [43, 3], [9, 82] and [10, 19].
  4. And again, down to 8 single numbers. That took 3 levels of halving (log2 8 = 3), and every one-number piece counts as sorted.
  5. Merge back up, always taking the smaller front number. A pair costs one comparison: [38] and [27] give [27, 38], [43] and [3] give [3, 43], [9] and [82] give [9, 82] and [10] and [19] give [10, 19].
  6. Merge [27, 38] with [3, 43] by comparing their fronts: 3 < 27, take 3; 27 < 43, take 27; 38 < 43, take 38; then 43 is left and copied. 4 numbers, 3 comparisons.
  7. Merge [9, 82] with [10, 19] by comparing their fronts: 9 < 10, take 9; 10 < 82, take 10; 19 < 82, take 19; then 82 is left and copied. 4 numbers, 3 comparisons.
  8. The last merge interleaves [3, 27, 38, 43] and [9, 10, 19, 82] into [3, 9, 10, 19, 27, 38, 43, 82] with 7 comparisons. Each of the 3 levels handles all 8 numbers once: O(n log n) time, plus O(n) space to merge into.

Merge Sort study plan

All 2 Merge Sort problems (2 hard) over 2 days, about 1 h 55 min in all — the pattern first, then easiest to hardest. Then move on to Divide and Conquer.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve this problem.

Day 2

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

Next topic: Divide and Conquer

Merge Sort: the essentials

When to reach for it

A sort that must be O(n log n) on every input, or stable, or on a linked list, or on data too large for memory. Above all here: counting pairs i < j whose values satisfy an order condition — inversions, nums[i] > 2 * nums[j], earlier values that are smaller — where brute force is O(n²) and n reaches 10⁵.

The pattern

Split in half, sort each half recursively, and merge with two pointers that take the smaller head. With both halves sorted, every cross pair has its left element earlier in the array, and a pointer moving only forward through the right half counts them for every left element in one pass; pairs inside a half were counted lower down. Count before merging when the condition differs from the merge's comparison, as in Reverse Pairs. A Binary Indexed Tree counts the same pairs one insertion at a time.

from heapq import merge

def reverse_pairs(nums):            # pairs i < j with nums[i] > 2 * nums[j]
    def go(a):                      # (a sorted, pairs inside a)
        if len(a) <= 1: return a, 0
        (L, x), (R, y) = go(a[:len(a) // 2]), go(a[len(a) // 2:])
        count, j = x + y, 0
        for v in L:                 # both halves sorted: j only moves forward
            while j < len(R) and v > 2 * R[j]: j += 1
            count += j
        return list(merge(L, R)), count     # the linear merge
    return go(nums)[1]

Cost

T(n) = 2T(n/2) + O(n): O(n log n) on every input, O(n) extra space, recursion O(log n) deep. Linked lists merge by relinking, with no buffer.

Common mistakes

  • Taking from the right half on a tie (< instead of <=), which makes the sort unstable.
  • Counting cross pairs after the merge, when an element's half is no longer known.
  • Overflow: 2 * nums[j] passes 2³¹ − 1 when values reach 10⁹; compute it in 64 bits.
  • With an inclusive hi, recursing on [lo, mid] and [mid, hi]: a two-element range never shrinks.

Start with

All merge sort problems

Hard (2)

Companies that ask merge sort problems

Next topic: Divide and Conquer