Learn to implement and apply advanced sorting algorithms: Merge Sort and Quick Sort.
function mergeSort(arr) {
// Base case: arrays with 0 or 1 element are already sorted
if (arr.length <= 1) {
return arr;
}
// Split array into two halves
const mid = Math.floor(arr.length / 2);
const left = arr.slice(0, mid);
const right = arr.slice(mid);
// Recursively sort both halves
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
const result = [];
let leftIndex = 0;
let rightIndex = 0;
// Compare elements from both arrays and merge them in sorted order
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] < right[rightIndex]) {
result.push(left[leftIndex]);
leftIndex++;
} else {
result.push(right[rightIndex]);
rightIndex++;
}
}
// Add remaining elements (if any)
return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}
const numbers = [38, 27, 43, 3, 9, 82, 10];
console.log(mergeSort(numbers)); // [3, 9, 10, 27, 38, 43, 82]
function quickSort(arr, left = 0, right = arr.length - 1) {
if (left < right) {
// Partition array and get pivot index
const pivotIndex = partition(arr, left, right);
// Recursively sort elements before and after pivot
quickSort(arr, left, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, right);
}
return arr;
}
function partition(arr, left, right) {
// Choose the rightmost element as the pivot
const pivot = arr[right];
let i = left - 1;
// Move all elements smaller than pivot to the left
for (let j = left; j < right; j++) {
if (arr[j] <= pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]]; // Swap elements
}
}
// Place pivot in its correct position
[arr[i + 1], arr[right]] = [arr[right], arr[i + 1]];
return i + 1; // Return pivot index
}
const numbers = [10, 7, 8, 9, 1, 5];
console.log(quickSort(numbers)); // [1, 5, 7, 8, 9, 10]
| Characteristic | Merge Sort | Quick Sort |
|---|---|---|
| Approach | Divide and conquer, merges sorted sublists | Divide and conquer, uses pivot to partition |
| Time Complexity | O(n log n) - consistent | Average: O(n log n), Worst: O(n²) |
| Space Complexity | O(n) - requires extra space | O(log n) - in-place partitioning |
| Stability | Stable (preserves order of equal elements) | Unstable (may change order of equal elements) |
| Best Use Cases | External sorting, linked lists, stability required | Internal sorting, arrays, memory constraints |
Test your understanding with these LeetCode problems: