Learn how merge sort uses divide and conquer to sort in guaranteed O(n log n) time.

Merge Sort

Merge sort uses divide and conquer — split the array in half, recursively sort each half, then merge the two sorted halves back together. Unlike bubble and selection sort, it guarantees O(n log n) in all cases.

Merge SortO(n log n) · divide and conquer

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

dividing

merging

merged

waiting

merge_sort.py

def merge_sort(arr):

split → left half, right half

merge(sorted_left, sorted_right)

place smaller element first

# subarray is now merged

return arr

Start merge sort — divide and conquer

step 0/39

How it works

def merge_sort(arr):
    if len(arr) <= 1:
        return arr   # base case — already sorted

    # divide
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    # conquer — merge the two sorted halves
    return merge(left, right)


def merge(left, right):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])
    return result

The divide and conquer structure

merge_sort([5, 3, 8, 1, 2])
  split → [5, 3] and [8, 1, 2]

  merge_sort([5, 3])
    split → [5] and [3]
    merge([5], [3]) → [3, 5]

  merge_sort([8, 1, 2])
    split → [8] and [1, 2]
    merge_sort([1, 2])
      split → [1] and [2]
      merge([1], [2]) → [1, 2]
    merge([8], [1, 2]) → [1, 2, 8]

  merge([3, 5], [1, 2, 8]) → [1, 2, 3, 5, 8]

The recursion goes all the way down to single-element arrays (which are trivially sorted), then merges back up.

Why O(n log n)

There are log n levels of splitting — each split halves the problem. At each level, the merge step does O(n) total work — comparing and placing every element exactly once. Total: O(n) × O(log n) = O(n log n).

Level 0:  [5, 3, 8, 1, 2]          — n=5 elements merged
Level 1:  [5, 3]    [8, 1, 2]       — n=5 elements merged total
Level 2:  [5][3]  [8] [1, 2]        — n=5 elements merged total
Level 3:  [5][3]  [8] [1][2]        — n=5 elements merged total

3 levels ≈ log₂(5). Each level merges n total. n × log n.

Merge sort is a stable sort — equal elements keep their original relative order. This matters when sorting records by multiple fields. It is also the basis for Python's Timsort, which uses merge sort for the large-scale combining step.

The tradeoff — extra memory

Merge sort requires O(n) extra space for the temporary arrays created during merging. Quicksort (next) avoids this by sorting in-place — but at the cost of O(n²) worst case performance.

Complexity

Case	Time	Space
Best	O(n log n)	O(n)
Average	O(n log n)	O(n)
Worst	O(n log n)	O(n)

Merge Sort

Merge Sort

How it works

The divide and conquer structure

Why O(n log n)

The tradeoff — extra memory

Complexity

On this page