Merge Sort

Merge sort is like splitting a big pile of homework in half again and again until each pile is one paper, then merging the small sorted piles back together.

In this page:

Basic Idea
Step by Step
Small Array
Practice
Summary

Syntax

markup

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

Basic Idea

Merge sort splits the array in half recursively until each piece has just one element, then merges those pieces back together in sorted order — a classic divide-and-conquer strategy where the hard work happens during the merge, not the split.

Example: Basic Idea

#include <iostream>
using namespace std;
void merge(int arr[], int l, int m, int r) {
	int n1 = m - l + 1, n2 = r - m, L[10], R[10];
	for (int i = 0; i < n1; i++) L[i] = arr[l + i];
	for (int i = 0; i < n2; i++) R[i] = arr[m + 1 + i];
	int i = 0, j = 0, k = l;
	while (i < n1 && j < n2) arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
	while (i < n1) arr[k++] = L[i++];
	while (j < n2) arr[k++] = R[j++];
}
void mergeSort(int arr[], int l, int r) {
	if (l >= r) return;
	int m = (l + r) / 2;
	mergeSort(arr, l, m);
	mergeSort(arr, m + 1, r);
	merge(arr, l, m, r);
}
int main() {
	int arr[] = {5, 1, 4, 2, 8};
	mergeSort(arr, 0, 4);
	for (int x : arr) cout << x << " ";
	return 0;
}

public class Main {
	static void merge(int[] arr, int l, int m, int r) {
		int n1 = m - l + 1, n2 = r - m;
		int[] L = new int[n1], R = new int[n2];
		for (int i = 0; i < n1; i++) L[i] = arr[l + i];
		for (int i = 0; i < n2; i++) R[i] = arr[m + 1 + i];
		int i = 0, j = 0, k = l;
		while (i < n1 && j < n2) arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
		while (i < n1) arr[k++] = L[i++];
		while (j < n2) arr[k++] = R[j++];
	}
	static void mergeSort(int[] arr, int l, int r) {
		if (l >= r) return;
		int m = (l + r) / 2;
		mergeSort(arr, l, m);
		mergeSort(arr, m + 1, r);
		merge(arr, l, m, r);
	}
	public static void main(String[] args) {
		int[] arr = {5, 1, 4, 2, 8};
		mergeSort(arr, 0, 4);
		System.out.println(java.util.Arrays.toString(arr));
	}
}

def merge(arr, l, m, r):
    left = arr[l:m + 1]
    right = arr[m + 1:r + 1]
    i = j = 0
    k = l
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            arr[k] = left[i]; i += 1
        else:
            arr[k] = right[j]; j += 1
        k += 1
    while i < len(left):
        arr[k] = left[i]; i += 1; k += 1
    while j < len(right):
        arr[k] = right[j]; j += 1; k += 1

def merge_sort(arr, l, r):
    if l >= r:
        return
    m = (l + r) // 2
    merge_sort(arr, l, m)
    merge_sort(arr, m + 1, r)
    merge(arr, l, m, r)

arr = [5, 1, 4, 2, 8]
merge_sort(arr, 0, 4)
print(arr)

#include <stdio.h>
void merge(int arr[], int l, int m, int r) {
	int n1 = m - l + 1, n2 = r - m, L[10], R[10];
	for (int i = 0; i < n1; i++) L[i] = arr[l + i];
	for (int i = 0; i < n2; i++) R[i] = arr[m + 1 + i];
	int i = 0, j = 0, k = l;
	while (i < n1 && j < n2) arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
	while (i < n1) arr[k++] = L[i++];
	while (j < n2) arr[k++] = R[j++];
}
void mergeSort(int arr[], int l, int r) {
	if (l >= r) return;
	int m = (l + r) / 2;
	mergeSort(arr, l, m);
	mergeSort(arr, m + 1, r);
	merge(arr, l, m, r);
}
int main() {
	int arr[] = {5, 1, 4, 2, 8};
	mergeSort(arr, 0, 4);
	for (int i = 0; i < 5; i++) printf("%d ", arr[i]);
	return 0;
}

Step by Step

The recursive split keeps halving the array until it can't be divided further; the real sorting work happens as pairs of already-sorted halves are merged back together by repeatedly taking the smaller of the two halves' front elements.

Example: Step by Step

#include <iostream>
using namespace std;
int main() {
	cout << "Split [5,1,4,2] -> [5,1] [4,2] -> [5] [1] [4] [2] -> merge back up sorted";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Split [5,1,4,2] -> [5,1] [4,2] -> [5] [1] [4] [2] -> merge back up sorted");
	}
}

print("Split [5,1,4,2] -> [5,1] [4,2] -> [5] [1] [4] [2] -> merge back up sorted")

#include <stdio.h>
int main() {
	printf("Split [5,1,4,2] -> [5,1] [4,2] -> [5] [1] [4] [2] -> merge back up sorted");
	return 0;
}

Small Array

Tracing the merge step on two small sorted halves like [1, 4] and [2, 3] shows exactly how comparing front elements and advancing one pointer at a time produces a single sorted sequence without needing to re-sort anything.

Example: Small Array

#include <iostream>
using namespace std;
int main() {
	int L[] = {1, 4}, R[] = {2, 3}, merged[4];
	int i = 0, j = 0, k = 0;
	while (i < 2 && j < 2) merged[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
	while (i < 2) merged[k++] = L[i++];
	while (j < 2) merged[k++] = R[j++];
	for (int x : merged) cout << x << " ";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[] L = {1, 4}, R = {2, 3}, merged = new int[4];
		int i = 0, j = 0, k = 0;
		while (i < 2 && j < 2) merged[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
		while (i < 2) merged[k++] = L[i++];
		while (j < 2) merged[k++] = R[j++];
		System.out.println(java.util.Arrays.toString(merged));
	}
}

L, R = [1, 4], [2, 3]
merged = []
i = j = 0
while i < 2 and j < 2:
    if L[i] <= R[j]:
        merged.append(L[i]); i += 1
    else:
        merged.append(R[j]); j += 1
merged += L[i:] + R[j:]
print(merged)

#include <stdio.h>
int main() {
	int L[] = {1, 4}, R[] = {2, 3}, merged[4];
	int i = 0, j = 0, k = 0;
	while (i < 2 && j < 2) merged[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
	while (i < 2) merged[k++] = L[i++];
	while (j < 2) merged[k++] = R[j++];
	for (int x = 0; x < 4; x++) printf("%d ", merged[x]);
	return 0;
}

Practice

Because merge sort splits evenly and does a fixed amount of merge work per level, its total running time stays predictable regardless of the input's initial order — try tracing it on both a sorted and a reverse-sorted array to see the merge steps stay the same either way.

Example: Practice

#include <iostream>
using namespace std;
int main() {
	int n = 8;
	cout << "Merge sort on " << n << " elements always does the same fixed amount of work per level";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int n = 8;
		System.out.println("Merge sort on " + n + " elements always does the same fixed amount of work per level");
	}
}

n = 8
print("Merge sort on", n, "elements always does the same fixed amount of work per level")

#include <stdio.h>
int main() {
	int n = 8;
	printf("Merge sort on %d elements always does the same fixed amount of work per level", n);
	return 0;
}

Summary

Merge sort guarantees O(n log n) time in every case (best, average, and worst), which is a meaningful improvement over bubble, selection, and insertion sort's O(n²) — the tradeoff is that merge sort needs O(n) extra space for the temporary merged arrays.

Example: Summary

#include <iostream>
using namespace std;
int main() {
	cout << "Merge sort: guaranteed O(n log n) in best, average, and worst case";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Merge sort: guaranteed O(n log n) in best, average, and worst case");
	}
}

print("Merge sort: guaranteed O(n log n) in best, average, and worst case")

#include <stdio.h>
int main() {
	printf("Merge sort: guaranteed O(n log n) in best, average, and worst case");
	return 0;
}

Chapter Quiz — Complete all 9 topics to unlock

0/9 topics done

Complete these topics first:

← Previous Lesson Insertion Sort Next Lesson → Quick Sort