Merge Sort
See the array split into halves, each half sorted, and the halves merged back together through an auxiliary array.
How it works
Merge sort is a divide and conquer algorithm. It splits the array into two halves, sorts each half by calling itself, and then merges the two sorted halves into one. A single element is already sorted, so the splitting stops there.
Merging needs somewhere to put values while they are being combined, so merge sort uses an auxiliary array (aux), shown as the second row:
- The range being merged is copied down into
aux. - Two pointers walk the left and right halves in
aux. Each step compares their values and copies the smaller one back up into the next slot of the array. - When one half runs out, the rest of the other half is copied back as it is.
When to use it
Merge sort is always O(n log n), whatever the input, and it is stable. It is the standard choice for sorting linked lists and for external sorting (data too big for memory), and it is the base of Timsort, the built-in sort in Python and JavaScript engines. Its cost is the extra O(n) memory for aux.
Complexity
It is stable: when two values are equal, the merge takes the one from the left half first, so equal values keep their order.
| Case | Time | When |
|---|---|---|
| Best | O(n log n) | Any order: it always splits and merges every level |
| Average | O(n log n) | Random order |
| Worst | O(n log n) | Any order: there are log n levels of O(n) merging |
| Extra space | Why |
|---|---|
| O(n) | The auxiliary array holds a copy of each range being merged, plus O(log n) for the recursion |
Implementations
function mergeSort(array, aux = new Array(array.length), lo = 0, hi = array.length - 1) {
if (lo >= hi) return array;
const mid = Math.floor((lo + hi) / 2);
mergeSort(array, aux, lo, mid);
mergeSort(array, aux, mid + 1, hi);
for (let k = lo; k <= hi; k++) aux[k] = array[k];
let i = lo;
let j = mid + 1;
for (let k = lo; k <= hi; k++) {
if (i > mid) array[k] = aux[j++];
else if (j > hi) array[k] = aux[i++];
else if (aux[j] < aux[i]) array[k] = aux[j++];
else array[k] = aux[i++];
}
return array;
}
def merge_sort(array):
a = list(array)
aux = [None] * len(a)
def sort(lo, hi):
if lo >= hi:
return
mid = (lo + hi) // 2
sort(lo, mid)
sort(mid + 1, hi)
aux[lo:hi + 1] = a[lo:hi + 1]
i, j = lo, mid + 1
for k in range(lo, hi + 1):
if i > mid:
a[k] = aux[j]; j += 1
elif j > hi:
a[k] = aux[i]; i += 1
elif aux[j] < aux[i]:
a[k] = aux[j]; j += 1
else:
a[k] = aux[i]; i += 1
sort(0, len(a) - 1)
return a
#include <vector>
void sort(std::vector<int>& a, std::vector<int>& aux, int lo, int hi) {
if (lo >= hi) return;
const int mid = lo + (hi - lo) / 2;
sort(a, aux, lo, mid);
sort(a, aux, mid + 1, hi);
for (int k = lo; k <= hi; k++) aux[k] = a[k];
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
if (i > mid) a[k] = aux[j++];
else if (j > hi) a[k] = aux[i++];
else if (aux[j] < aux[i]) a[k] = aux[j++];
else a[k] = aux[i++];
}
}
std::vector<int> mergeSort(std::vector<int> a) {
std::vector<int> aux(a.size());
sort(a, aux, 0, static_cast<int>(a.size()) - 1);
return a;
}