Merge Sort Complete Guide
5.0|1 ratingLog in to rate
A comprehensive guide to understanding and implementing Merge Sort with time complexity analysis.
#sorting#divide-and-conquer#recursion
What is Merge Sort?
Merge Sort is a divide-and-conquer algorithm that recursively splits an array in half, sorts the individual halves, and then merges them back together. It has guaranteed O(n log n) runtime performance.
JavaScript Merge Sort Implementation
javascript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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, j = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) result.push(left[i++]);
else result.push(right[j++]);
}
return [...result, ...left.slice(i), ...right.slice(j)];
}Discussion
Loading discussion...