Medium Sorting
Merge Sort
Receives an array of integers and returns a new array sorted in ascending order. It uses divide-and-conquer: it splits the array in half, recursively sorts each half, then merges the two sorted halves by comparing their front elements one at a time — always picking the smaller one — and appending any remainder. Guarantees O(n log n) time in all cases. Returns a new array; the original is not modified.
Visualization
- Input
- Result
Algorithm code
// Merge Sort — a single pure function. Receives an array of integers and
// returns a new array sorted in ascending order, using divide-and-conquer:
// it splits the array in half, recursively sorts each half, then merges them.
/**
* @param {number[]} arr - array of integers to sort
* @returns {number[]} a new array with the values in ascending order
*/
export function mergeSort(arr) {
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);
}
function merge(left, right) {
const result = [];
let i = 0;
let j = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
result.push(left[i]);
i += 1;
} else {
result.push(right[j]);
j += 1;
}
}
return result.concat(left.slice(i), right.slice(j));
}FUNCTION mergeSort(arr):
IF length(arr) ≤ 1:
RETURN copy(arr)
mid ← floor(length(arr) / 2)
left ← mergeSort(arr[0..mid-1])
right ← mergeSort(arr[mid..end])
RETURN merge(left, right)
FUNCTION merge(left, right):
result ← []
i ← 0, j ← 0
WHILE i < length(left) AND j < length(right):
IF left[i] ≤ right[j]:
APPEND left[i] TO result
i ← i + 1
ELSE:
APPEND right[j] TO result
j ← j + 1
APPEND left[i..] TO result
APPEND right[j..] TO result
RETURN result