Merge Sort
In this page:
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;
}Login to try C/C++/Java code in the editor
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;
}Login to try C/C++/Java code in the editor
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;
}Login to try C/C++/Java code in the editor
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;
}Login to try C/C++/Java code in the editor
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;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 9 topics to unlock
0/9 topics done
Complete these topics first: