Divide & Conquer

Merge Sort

Split the array in half, recursively sort each half, then merge the two sorted halves into one. Merging two sorted arrays is O(n). Since we split log n times, total is O(n log n). Stable sort.

O(n log n)

O(n)

How It Works

Merge sort embodies divide and conquer in its purest form: split the array at the midpoint, recursively sort each half, then merge the two sorted halves with two pointers, always copying the smaller front element into the output. The merge is linear, and the base case is a single element, which is trivially sorted.

The recursion halves the input log n times, and each level performs O(n) total merging work, giving a guaranteed O(n log n) — no bad cases, unlike quicksort's O(n^2) worst case. It is also stable: equal elements keep their relative order because the merge takes from the left half on ties. The costs are O(n) auxiliary space for the merge buffer and non-in-place operation. The merge step itself is a reusable interview primitive, powering count-inversions, count of smaller after self, and external sorting of datasets too large for memory.

Step-by-Step Visualization

Divide and conquer: merge sort

Split[5,2] | [4,1,3]

1/3

Code

Java

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

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

Tips & Gotchas

1Split problem in half, solve each half, combine results

2Merge step is key: combine two sorted halves in O(n)

3Also useful for counting inversions (count during merge)

Practice Problems

1Sort an Array
2Merge Two Sorted Lists
3Sort List
4Count of Smaller Numbers After Self
5Reverse Pairs

About the Divide & Conquer Pattern

Split the problem into two (or more) smaller subproblems, solve each independently, then combine the results. The splitting usually halves the input, giving O(n log n) algorithms.

Key insight

Every recursive solution has: base case, recursive case, and combining step. For backtracking, add: make choice → recurse → undo choice. Prune early to avoid TLE.

Common Recursion Interview Problems

Subsets
Permutations
Combination Sum
N-Queens
Word Search
Generate Parentheses
Letter Combinations of Phone Number

Frequently Asked Questions

When does merge sort beat quicksort in practice?

When you need a guaranteed O(n log n) bound, stability, or are sorting linked lists — merging lists needs no random access and O(1) extra space. Quicksort tends to win on arrays in average-case constant factors and cache behavior, which is why hybrid library sorts often use both ideas.

How does merge sort count inversions as a side effect?

During the merge, whenever an element from the right half is placed before remaining elements of the left half, it is smaller than all of them, so add the count of remaining left elements to the inversion total. The count accumulates across all merges at no extra asymptotic cost, solving the problem in O(n log n).

Why does merge sort need O(n) extra space, and can that be avoided?

Merging two adjacent sorted runs in place without extra memory forces expensive element shifting, so a scratch buffer of size n keeps the merge linear. In-place variants exist but are complex and slower in practice; for linked lists, though, merging is naturally O(1) space since only pointers change.