Loading...
A stable, divide-and-conquer algorithm that consistently delivers O(n log n) performance. It divides the array into halves, sorts them recursively, and merges the sorted halves.
function mergeSort(arr) {
// Base case: arrays with 0 or 1 element are sorted
if (arr.length <= 1) return arr;
// Divide: split array in half
const mid = Math.floor(arr.length / 2);
const left = arr.slice(0, mid);
const right = arr.slice(mid);
// Conquer: recursively sort both halves
const leftSorted = mergeSort(left);
const rightSorted = mergeSort(right);
// Combine: merge the sorted halves
return merge(leftSorted, rightSorted);
}
function merge(left, right) {
const result = [];
let i = 0, j = 0;
// Compare elements and merge in sorted order
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
result.push(left[i]);
i++;
} else {
result.push(right[j]);
j++;
}
}
// Add remaining elements
return result.concat(left.slice(i)).concat(right.slice(j));
}
// Time: O(n log n) - always
// Space: O(n) - temporary arraysfunction mergeSortInPlace(arr, left = 0, right = arr.length - 1) {
if (left >= right) return;
const mid = Math.floor((left + right) / 2);
mergeSortInPlace(arr, left, mid);
mergeSortInPlace(arr, mid + 1, right);
mergeInPlace(arr, left, mid, right);
}
function mergeInPlace(arr, left, mid, right) {
// Create temporary arrays
const leftArr = arr.slice(left, mid + 1);
const rightArr = arr.slice(mid + 1, right + 1);
let i = 0, j = 0, k = left;
while (i < leftArr.length && j < rightArr.length) {
if (leftArr[i] <= rightArr[j]) {
arr[k++] = leftArr[i++];
} else {
arr[k++] = rightArr[j++];
}
}
while (i < leftArr.length) arr[k++] = leftArr[i++];
while (j < rightArr.length) arr[k++] = rightArr[j++];
}function mergeSortBottomUp(arr) {
const n = arr.length;
// Start with subarray size 1, double each iteration
for (let size = 1; size < n; size *= 2) {
// Merge subarrays of current size
for (let left = 0; left < n - size; left += 2 * size) {
const mid = left + size - 1;
const right = Math.min(left + 2 * size - 1, n - 1);
mergeInPlace(arr, left, mid, right);
}
}
return arr;
}
// Iterative approach
// No recursion - uses loops instead
// Same time complexity: O(n log n)
// Space: O(n) for temporary arraysAlways divides array into log n levels, with n work per level. Performance is predictable regardless of input order.
Requires temporary arrays for merging. Not an in-place algorithm, but space usage is linear and predictable.