Merge Sort Algorithm: Divide and Conquer, O(n log n), and Stable Sort (2026)
Merge Sort is a classic divide-and-conquer sorting algorithm. It divides the unsorted list into n sublists (each containing one element), then repeatedly merges sublists to produce new sorted sublists until only one sorted list remains. Its guaranteed O(n log n) time complexity makes it one of the most reliable general-purpose sorting algorithms.
This tutorial covers the divide-and-conquer approach, the merge operation, complexity analysis, and the stable sorting property with implementations in C++, Java, and Python.
Divide and Conquer Strategy
Merge Sort recursively divides the array into two halves until each subarray contains a single element (which is trivially sorted). It then merges the sorted halves back together. The merge operation combines two sorted arrays into one sorted array by repeatedly comparing the front elements and picking the smaller one.
The recurrence relation is T(n) = 2T(n/2) + O(n), which solves to O(n log n) using the Master Theorem. Merge Sort requires O(n) auxiliary space for the temporary arrays used during merging. It is a stable sort because when equal elements are encountered during merging, the element from the left subarray is placed first, preserving the original order.
// C++
void merge(int arr[], int l, int m, int r) {
int n1 = m-l+1, n2 = r-m;
int L[n1], R[n2];
for(int i=0; i= r) return;
int m = l + (r-l)/2;
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
// Java — similar recursive approach
// Python
def merge_sort(arr):
if len(arr) <= 1: return arr
m = len(arr)//2
L, R = merge_sort(arr[:m]), merge_sort(arr[m:])
res = []
i = j = 0
while i < len(L) and j < len(R):
if L[i] <= R[j]: res.append(L[i]); i+=1
else: res.append(R[j]); j+=1
return res + L[i:] + R[j:] Complexity and Space Analysis
Merge Sort guarantees O(n log n) time in all cases (best, average, worst). This makes it predictable and reliable for large datasets. The space complexity is O(n) — the merge operation requires temporary arrays. There are in-place merge sort variants, but they are complex and often sacrifice the stable property or degrade performance.
Because of its O(n) space requirement, Merge Sort is typically used for sorting linked lists (where O(1) space is possible) or for external sorting (where data is too large to fit in memory). Many language libraries use Timsort (a hybrid of Merge Sort and Insertion Sort) for general-purpose sorting.
// C++ — merge operation creates temp arrays
// Space: O(n) for the temp arrays
void merge(vector& arr, int l, int m, int r) {
vector temp(r-l+1);
int i=l, j=m+1, k=0;
while(i<=m && j<=r)
temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
while(i<=m) temp[k++] = arr[i++];
while(j<=r) temp[k++] = arr[j++];
for(int p=0; p Frequently Asked Questions
Is Merge Sort stable?
Yes, Merge Sort is stable. The merge operation places elements from the left subarray first when equal, preserving the original relative order.
Why is Merge Sort preferred for sorting linked lists?
Linked lists do not require O(n) extra space for merging because nodes can be rearranged by changing pointers. Merge Sort is the preferred algorithm for linked lists.
Originally published on Ayodhyyya. Last updated June 1, 2026.