Skills101

AdvancedData Structures & Algorithms · Lesson 17 of 20 · Updated ·

Merge Sort and Quick Sort — Divide and Conquer Sorting

Bubble, selection and insertion sort are O(n²). To sort 10⁵ or 10⁶ items you need O(n log n). The two classic ways to get there both use divide and conquer: break the problem into smaller copies of itself, solve those, and combine the answers.

  • Merge sort: split the array in half, sort each half, then merge the two sorted halves.
  • Quick sort: pick a pivot, move smaller items to its left and larger to its right, then sort each side.

1. Merge sort

Merge sort on 6 3 8 1 5 2 7 4: the array is split into halves three times down to pairs, then merged back: 3 6, 1 8, 2 5, 4 7, then 1 3 6 8 and 2 4 5 7, and finally 1 2 3 4 5 6 7 8

The real work happens in the merge step. Two sorted lists are combined by repeatedly taking the smaller front item:

def merge(left, right):
    out, i, k = [], 0, 0
    while i < len(left) and k < len(right):
        if left[i] <= right[k]:          # <= keeps equal items in order (stable)
            out.append(left[i]); i += 1
        else:
            out.append(right[k]); k += 1
    return out + left[i:] + right[k:]    # one side may still have items

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

print(merge([1, 3, 6, 8], [2, 4, 5, 7]))
print(merge_sort([6, 3, 8, 1, 5, 2, 7, 4]))
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]

Why O(n log n)? Halving 8 items reaches size 1 after log₂ 8 = 3 levels. On each level, the merges together touch all n items once. So the total is n × log n — and that holds in the best, average and worst case.

Cost: merge sort needs O(n) extra memory for the merged lists. It is stable, which is why Java uses a merge-sort variant (Timsort) for sorting objects.

2. Quick sort

Quick sort does its work before recursing. The partition step picks a pivot and rearranges the array so that every smaller item comes before it and every larger item after it. The pivot is then in its final position.

Lomuto partition of 7 2 9 4 3 8 5 with pivot 5: after partitioning the array is 2 4 3 5 9 8 7, smaller items on the left, the pivot 5 at its final index 3, larger items on the right

This is the Lomuto partition — the easiest version to write in an interview:

def partition(a, lo, hi):
    pivot = a[hi]
    i = lo - 1                      # a[lo..i] holds items smaller than the pivot
    for k in range(lo, hi):
        if a[k] < pivot:
            i += 1
            a[i], a[k] = a[k], a[i]
    a[i + 1], a[hi] = a[hi], a[i + 1]
    return i + 1

def quick_sort(a, lo=0, hi=None):
    if hi is None:
        hi = len(a) - 1
    if lo < hi:
        p = partition(a, lo, hi)
        quick_sort(a, lo, p - 1)
        quick_sort(a, p + 1, hi)
    return a

b = [7, 2, 9, 4, 3, 8, 5]
print(partition(b, 0, len(b) - 1), b)
print(quick_sort([7, 2, 9, 4, 3, 8, 5]))
3 [2, 4, 3, 5, 9, 8, 7]
[2, 3, 4, 5, 7, 8, 9]

Quick sort's worst case

If the pivot is always the smallest or largest item — for example, the last element of an already sorted array — each partition removes only one item. That gives n levels of n work: O(n²).

The fix is to choose the pivot randomly (swap a random item to the end first). Then the expected time is O(n log n) on every input. Quick sort sorts in place (only O(log n) stack space on average) and is very fast in practice, so Java's Arrays.sort for primitive arrays uses a quick sort variant (dual-pivot quick sort).

Quick sort in Java (random pivot)

import java.util.Arrays;
import java.util.Random;

public class Main {
    static Random rnd = new Random(42);

    static int partition(int[] a, int lo, int hi) {
        int r = lo + rnd.nextInt(hi - lo + 1);       // random pivot → expected O(n log n)
        int t = a[r]; a[r] = a[hi]; a[hi] = t;
        int pivot = a[hi], i = lo - 1;
        for (int k = lo; k < hi; k++) {
            if (a[k] < pivot) {
                i++;
                t = a[i]; a[i] = a[k]; a[k] = t;
            }
        }
        t = a[i + 1]; a[i + 1] = a[hi]; a[hi] = t;
        return i + 1;
    }

    static void quickSort(int[] a, int lo, int hi) {
        if (lo >= hi) return;
        int p = partition(a, lo, hi);
        quickSort(a, lo, p - 1);
        quickSort(a, p + 1, hi);
    }

    public static void main(String[] args) {
        int[] a = {10, 80, 30, 90, 40, 50, 70};
        quickSort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));
    }
}
[10, 30, 40, 50, 70, 80, 90]

3. Merge sort vs quick sort

Merge sortQuick sort
Time (worst)O(n log n)O(n²), rare with a random pivot
Time (average)O(n log n)O(n log n), usually faster in practice
Extra memoryO(n)O(log n) for recursion
Stable?yesno
Good forlinked lists, stable sorting, huge files on diskarrays in memory

4. Patterns built on these ideas

  • Merge step: "merge two sorted arrays", "merge k sorted lists" and counting inversions (count pairs while merging).
  • Partition step: quickselect finds the k-th smallest item in O(n) on average — partition, then recurse into only the side that contains index k.
  • Sort first, then solve: many problems (meeting rooms, two-sum on a sorted array, intervals) become easy after an O(n log n) sort.

Common mistakes

  • Writing < instead of <= in merge — the result is still sorted, but the sort is no longer stable.
  • Forgetting to copy the leftovers (left[i:], right[k:]) after the merge loop.
  • Quick sort recursing on (lo, p) instead of (lo, p − 1) — the pivot is already in place, and including it can recurse forever.
  • Using the last element as pivot on sorted input and getting O(n²) — pick a random pivot.

Quick recap

  • Both are divide and conquer and run in O(n log n) on average.
  • Merge sort: split, sort halves, merge; always O(n log n); stable; O(n) extra memory.
  • Quick sort: partition around a pivot, then sort both sides; in place; worst case O(n²) — use a random pivot.
  • The merge step and the partition step are themselves interview patterns.

Practice what you learned

📝 Quiz: Merge Sort and Quick Sort5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →