loading
loading
loading
Computer Science / Algorithms
Recursively split the array in half, then merge the sorted halves back together — guaranteed O(n log n), at the cost of O(n) auxiliary space.
Merge sort splits the array in half, recursively sorts each half, then merges the two already-sorted halves back into one sorted run — comparing their front elements one at a time and writing the smaller into a temporary merge buffer until both halves are exhausted. Because the split step does no comparisons at all and the merge step always halves the problem, merge sort guarantees O(n log n) time no matter how the input is ordered — unlike Quick Sort, whose last-element pivot degrades to O(n²) on already-sorted input. That guarantee isn't free: merging needs a full-size auxiliary buffer alongside the original array, so merge sort costs O(n) extra space, where Quick Sort's in-place partitioning costs only O(log n) on average. Watch the merge buffer (the dashed row) fill left to right as each comparison resolves — that's the actual work; the colored bars above it show which half of the current range each position belongs to. Press Shuffle to generate a new random array and watch the split-then-merge process repeat.
Merge sort's split step is unconditional — it always cuts the range exactly in half, regardless of the data — so there's no input order that can produce an unbalanced split the way an unlucky pivot choice can in quick sort. The log n factor comes from the guaranteed halving; the n factor comes from every element being touched once per merge level.
Merging two sorted runs in place, without a separate buffer, isn't possible to do efficiently — you'd overwrite values you still need to compare. Quick sort's partition avoids this because it only ever swaps elements within the original array, never needing a second copy of the data.
A stable sort preserves the relative order of elements that compare equal. This implementation's merge step always takes from the left run when the two front elements are equal (comparing with ≤, not <), so an element that started earlier in the array never ends up after an equal element that started later.