ayodhyya.comMerge 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 Ayodhyya. Last updated June 1, 2026.
Divide and Conquer Strategy
Merge sort splits the array in half recursively until subarrays have length one (trivially sorted), then merges them back in sorted order. The merge step runs in O(n) and the recursion depth is O(log n), giving O(n log n) in all cases.
Why Merge Sort Beats Quick Sort for Linked Lists
Merge sort accesses elements sequentially, making it ideal for linked lists where random access is expensive. Quick sort's partition step requires bidirectional traversal, which is slow on singly linked lists.
External Sorting
When data exceeds memory, merge sort is the foundation of external sorting: sort chunks in memory, write them to disk, then merge the runs. This is how database systems and big-data frameworks sort terabytes of data.
Bottom-Up (Iterative) Merge Sort
The iterative version starts with subarrays of size 1 and doubles the size each pass, eliminating recursion overhead. This is often faster in practice and easier to parallelize.
Divide and Conquer Strategy
Merge sort splits the array in half recursively until subarrays have length one (trivially sorted), then merges them back in sorted order. The merge step runs in O(n) and the recursion depth is O(log n), giving O(n log n) in all cases.<\/p>
Why Merge Sort Beats Quick Sort for Linked Lists
Merge sort accesses elements sequentially, making it ideal for linked lists where random access is expensive. Quick sort's partition step requires bidirectional traversal, which is slow on singly linked lists.<\/p>
External Sorting
When data exceeds memory, merge sort is the foundation of external sorting: sort chunks in memory, write them to disk, then merge the runs. This is how database systems and big-data frameworks sort terabytes of data.<\/p>
Bottom-Up (Iterative) Merge Sort
The iterative version starts with subarrays of size 1 and doubles the size each pass, eliminating recursion overhead. This is often faster in practice and easier to parallelize.<\/p>