Merge Sort
MediumMerge Sort is a divide-and-conquer algorithm that divides the input list into halves, sorts them recursively, and then merges them back together. It guarantees O(n log n) time complexity.
Time Complexity
O(n log n)Space Complexity
O(n)Category
Sorting
Introduction to Merge Sort
Merge Sort is a highly efficient sorting algorithm that uses the divide-and-conquer paradigm. It's one of the most important algorithms in computer science and forms the basis for external sorting and many database operations.
How It Works
The algorithm works in two phases:
**Divide Phase**:
1. Divide the array into two halves
2. Recursively divide each half until you have single elements
3. Continue until the entire array is divided
**Conquer/Merge Phase**:
1. Compare elements from both halves
2. Pick the smaller element and add to result array
3. Move the pointer of the array from which element was taken
4. Repeat until all elements are merged
Algorithm Complexity
Best and Worst Cases
Advantages
1. Guaranteed O(n log n) performance
2. Stable sorting algorithm
3. Predictable behavior
4. Good for linked lists
5. Suitable for external sorting (large datasets on disk)
Disadvantages
1. Requires O(n) extra space
2. Not in-place sorting
3. Higher constant factors than quicksort
4. Slower for small arrays due to overhead
When to Use
Comparison with Quicksort
Applications
Key Takeaways
- Divide-and-conquer approach
- Stable sorting
- Requires additional space
- Consistent performance
- Suitable for large datasets
- Widely used in practice
Implementation
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 = [];
while (left.length && right.length) {
if (left[0] <= right[0]) result.push(left.shift());
else result.push(right.shift());
}
return [...result, ...left, ...right];
}