Merge Sort - Implementation
Implementation
Let’s code merge sort. It’s elegant with recursion.
Complete Implementation
function mergeSort(arr) {
// Base case
if (arr.length <= 1) {
return arr;
}
// Divide
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
// Conquer (merge)
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]);
i++;
} else {
result.push(right[j]);
j++;
}
}
return result.concat(left.slice(i)).concat(right.slice(j));
}
def merge_sort(arr):
# Base case
if len(arr) <= 1:
return arr
# Divide
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
# Conquer (merge)
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
return result + left[i:] + right[j:]
Try It Yourself
🟨 JavaScript Merge Sort Implementation
📟 Console Output
Run code to see output...
Code Explanation
- Base case: Array with 0 or 1 element is already sorted
- Divide: Split array into two halves
- Recurse: Sort each half recursively
- Merge: Combine sorted halves using merge function
Edge Cases
- Empty array: Returns empty array (base case)
- Single element: Returns as-is (base case)
- Already sorted: Still divides and merges (but merge is efficient)
What’s Next?
Now that you can implement it, let’s analyze its performance and complexity.
Progress 71%
Page 5 of 7
← Previous
→ Next
Discussion
Loading comments...