Merge sort is divide and conquer: split the array in half, sort each half (the same way, recursively), and then merge the two sorted halves into one. Splitting continues until each piece has one value — and one value is always sorted.
Merging is the heart of it, and it's fast because both halves are already sorted: the smallest remaining value is always at the front of one of them, so each step is one comparison.
The array is split down to single values, then merged back up — each merge takes the smaller front value.
function mergeSort(nums) { if (nums.length <= 1) return nums; // one value is already sorted const mid = Math.floor(nums.length / 2); const left = mergeSort(nums.slice(0, mid)); // sort each half... const right = mergeSort(nums.slice(mid)); return merge(left, right); // ...then merge them} function merge(left, right) { const out = []; let i = 0, j = 0; while (i < left.length && j < right.length) { if (left[i] <= right[j]) out.push(left[i++]); // <= keeps equal values in order: stable else out.push(right[j++]); } while (i < left.length) out.push(left[i++]); while (j < right.length) out.push(right[j++]); return out;}Halving n repeatedly reaches 1 after about log₂ n levels, and at every level the merges together touch all n values once. So merge sort is O(n log n) — in the best, average and worst case alike; its running time doesn't depend on the input's order. The merged arrays need O(n) extra space (plus O(log n) for the recursion).
<=), so equal values keep their order.When you need a guaranteed O(n log n), a stable sort, or you're sorting a linked list or data too big for memory (merging sorted chunks from disk is external sorting). Python's and Java's object sort, Timsort, is a merge sort that also detects already-sorted runs.
The merge step is a pattern of its own: merging sorted lists, counting inversions and Reverse Pairs all reuse it — they're in the last chapter of this course.