Merge Sort

divide-and-conquerstablenot-in-place

Press play to start

1function mergeSort(arr: number[]): number[] {
if (arr.length <= 1) return arr
const mid = Math.floor(arr.length / 2)
const left = mergeSort(arr.slice(0, mid))
const right = mergeSort(arr.slice(mid))
return merge(left, right)
7}
8function merge(left: number[], right: number[]): number[] {
const result: number[] = []
let i = 0, j = 0
while (i < left.length && j < right.length)
  result.push(left[i] <= right[j] ? left[i++] : right[j++])
return result.concat(left.slice(i), right.slice(j))
14}

Step 1/0

Custom array:

Complexity

Best:O(n log n)
Average:O(n log n)
Worst:O(n log n)
Space:O(n)

Description

A divide-and-conquer algorithm that recursively splits the array in half, sorts each half, then merges them back together in sorted order.

When to use

Reliable O(n log n) for any input. Preferred for linked lists, stable sorting, and external sorting of large datasets.