Merge Sort
Last updated
Merge sort is a divide-and-conquer algorithm. It recursively splits the array in half until each piece has a single element (which is trivially sorted), then merges the pieces back together in order. The merge step walks two sorted subarrays with two pointers, always copying the smaller front element next. Press play above to watch the array get rebuilt merge by merge.
Because it always splits in half, merge sort runs in O(n log n) time in every case - its worst case is as good as its best. The trade-off is O(n) extra space for the temporary merge buffer.
Time & space complexity
| Case | Complexity | Notes |
|---|---|---|
| Best case | O(n log n) | Always halves the input |
| Average case | O(n log n) | Random order |
| Worst case | O(n log n) | Guaranteed - no bad inputs |
| Space | O(n) | Temporary buffer for merging |
| Stable | Yes | Ties resolved left-first during merge |
Step by step
| Step | What happens |
|---|---|
| 1 | If the range has 0 or 1 elements, it is already sorted. |
| 2 | Split the range into two halves. |
| 3 | Recursively merge-sort the left half. |
| 4 | Recursively merge-sort the right half. |
| 5 | Merge the two sorted halves with two pointers. |
Worked example
Sorting [5, 2, 4, 1]:
| Pass | Array | Action |
|---|---|---|
| Split | [5, 2] | [4, 1] | Divide the array into two halves |
| Split | [5] [2] | [4] [1] | Divide again until each piece is a single element |
| Merge | [2, 5] | [1, 4] | Merge [5],[2] into [2, 5] and [4],[1] into [1, 4] |
| Merge | [1, 2, 4, 5] | Merge [2, 5] and [1, 4]: pick 1, then 2, then 4, then 5 |
| Done | [1, 2, 4, 5] | Array is fully sorted |
When to use merge sort
| Use it when | Avoid it when |
|---|---|
You need a guaranteed O(n log n) worst case | Memory is tight and O(n) extra space is unacceptable |
| Stability matters (equal keys keep their order) | You are sorting small arrays where insertion sort is faster |
| You are sorting a linked list | In-place sorting is a hard requirement |
| Data is too large for RAM (external sorting) | Cache locality dominates and quicksort's in-place passes win |
Merge Sort code
A clean, runnable Merge Sort implementation in Python, JavaScript, Java, C++, C. Pick a language, copy the code, or open it pre-loaded in the Coddy Playground.
Merge Sort code in Python
Python
1def merge_sort(a):2 if len(a) <= 1:3 return a4 mid = len(a) // 25 left = merge_sort(a[:mid])6 right = merge_sort(a[mid:])7 return merge(left, right)8
9
10def merge(left, right):11 out = []12 i = j = 013 while i < len(left) and j < len(right):14 if left[i] <= right[j]:15 out.append(left[i])16 i += 117 else:18 out.append(right[j])19 j += 120 out.extend(left[i:])21 out.extend(right[j:])22 return out23
24
25nums = [38, 27, 43, 3, 9, 82, 10]26print("Before:", nums)27print("After: ", merge_sort(nums))Merge Sort code in JavaScript
JavaScript
1function mergeSort(arr) {2 if (arr.length <= 1) return arr;3 const mid = Math.floor(arr.length / 2);4 const left = mergeSort(arr.slice(0, mid));5 const right = mergeSort(arr.slice(mid));6 return merge(left, right);7}8
9// Merge two sorted arrays into one sorted array10function merge(left, right) {11 const out = [];12 let i = 0;13 let j = 0;14 while (i < left.length && j < right.length) {15 out.push(left[i] <= right[j] ? left[i++] : right[j++]);16 }17 return out.concat(left.slice(i), right.slice(j));18}19
20const data = [5, 2, 9, 1, 7, 3];21console.log("Before:", data);22console.log("Sorted:", mergeSort(data));Merge Sort code in Java
Java
1import java.util.Arrays;2
3public class Main {4 static void mergeSort(int[] arr, int left, int right) {5 if (left >= right) return;6 int mid = (left + right) / 2;7 mergeSort(arr, left, mid);8 mergeSort(arr, mid + 1, right);9 merge(arr, left, mid, right);10 }11
12 // Merge two sorted halves into a temp array, then copy back13 static void merge(int[] arr, int left, int mid, int right) {14 int[] tmp = new int[right - left + 1];15 int i = left, j = mid + 1, k = 0;16 while (i <= mid && j <= right) {17 tmp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];18 }19 while (i <= mid) tmp[k++] = arr[i++];20 while (j <= right) tmp[k++] = arr[j++];21 System.arraycopy(tmp, 0, arr, left, tmp.length);22 }23
24 public static void main(String[] args) {25 int[] arr = {38, 27, 43, 3, 9, 82, 10};26 System.out.println("Before: " + Arrays.toString(arr));27 mergeSort(arr, 0, arr.length - 1);28 System.out.println("After: " + Arrays.toString(arr));29 }30}Merge Sort code in C++
C++
1#include <iostream>2#include <vector>3
4void printVec(const std::vector<int>& a) {5 for (int x : a) std::cout << x << " ";6 std::cout << "\n";7}8
9void merge(std::vector<int>& a, int lo, int mid, int hi) {10 std::vector<int> tmp;11 tmp.reserve(hi - lo + 1);12 int i = lo, j = mid + 1;13 while (i <= mid && j <= hi) {14 if (a[i] <= a[j]) tmp.push_back(a[i++]);15 else tmp.push_back(a[j++]);16 }17 while (i <= mid) tmp.push_back(a[i++]);18 while (j <= hi) tmp.push_back(a[j++]);19 for (size_t k = 0; k < tmp.size(); ++k) a[lo + k] = tmp[k];20}21
22void mergeSort(std::vector<int>& a, int lo, int hi) {23 if (lo >= hi) return;24 int mid = lo + (hi - lo) / 2;25 mergeSort(a, lo, mid); // sort the left half26 mergeSort(a, mid + 1, hi); // sort the right half27 merge(a, lo, mid, hi); // merge the sorted halves28}29
30int main() {31 std::vector<int> data = {38, 27, 43, 3, 9, 82, 10};32 std::cout << "Before: ";33 printVec(data);34 mergeSort(data, 0, static_cast<int>(data.size()) - 1);35 std::cout << "After: ";36 printVec(data);37 return 0;38}Merge Sort code in C
C
1#include <stdio.h>2#include <stdlib.h>3
4void printArr(const int a[], int n) {5 for (int i = 0; i < n; i++) printf("%d ", a[i]);6 printf("\n");7}8
9void merge(int a[], int lo, int mid, int hi) {10 int* tmp = malloc((hi - lo + 1) * sizeof(int));11 int i = lo, j = mid + 1, k = 0;12 while (i <= mid && j <= hi) {13 if (a[i] <= a[j]) tmp[k++] = a[i++];14 else tmp[k++] = a[j++];15 }16 while (i <= mid) tmp[k++] = a[i++];17 while (j <= hi) tmp[k++] = a[j++];18 for (k = 0; k <= hi - lo; k++) a[lo + k] = tmp[k];19 free(tmp);20}21
22void mergeSort(int a[], int lo, int hi) {23 if (lo >= hi) return;24 int mid = lo + (hi - lo) / 2;25 mergeSort(a, lo, mid); // sort the left half26 mergeSort(a, mid + 1, hi); // sort the right half27 merge(a, lo, mid, hi); // merge the sorted halves28}29
30int main(void) {31 int data[] = {38, 27, 43, 3, 9, 82, 10};32 int n = sizeof(data) / sizeof(data[0]);33 printf("Before: ");34 printArr(data, n);35 mergeSort(data, 0, n - 1);36 printf("After: ");37 printArr(data, n);38 return 0;39}Merge Sort FAQ
What is the time complexity of merge sort?
Merge sort is
O(n log n) in the best, average, and worst cases, because it always divides the array in half. It uses O(n) extra space for the merge buffer.Is merge sort stable?
Yes, when the merge step resolves ties by taking from the left half first. This keeps equal elements in their original relative order, which is why merge sort is a common choice for stable sorting.
Why use merge sort over quicksort?
Merge sort guarantees
O(n log n) even on adversarial inputs and is stable, whereas quicksort can degrade to O(n²). Merge sort is also preferred for linked lists and external sorting. The downside is its O(n) extra memory.What is the difference between merge sort and quicksort?
Both are divide-and-conquer sorts, but quicksort partitions around a pivot and sorts in place with
O(log n) stack space, while merge sort splits blindly in half and merges using an O(n) buffer. Quicksort is usually faster in practice due to cache locality, but merge sort has a guaranteed O(n log n) worst case and is stable.When should I use merge sort in practice?
Reach for merge sort when you need a stable sort with a guaranteed
O(n log n) bound, when sorting linked lists (where it needs no random access), or when doing external sorting of data too large to fit in memory. Avoid it when memory is scarce, since it needs O(n) extra space.Does merge sort sort in place?
No. Standard merge sort allocates an
O(n) temporary buffer to merge the two halves, so it is not in-place. In-place merge variants exist but are complex and either slower or lose stability, so the buffer-based version is the common choice.Related resources
More visualizations
