Set your Publisher ID in src/config/ads.ts to display live ads.
Sorting Algorithms: QuickSort & MergeSort
Divide-and-Conquer, partition pivot strategies, stability, and O(n log n)
Sorting arranges elements in ascending or descending sequence. Efficient divide-and-conquer algorithms sort in O(n log n) time.
QuickSort vs MergeSort
MergeSort: Divides the array in half recursively until single-element arrays remain, then merges sorted halves back together. Guarantees O(n log n) worst-case time, but requires O(n) extra memory space.
QuickSort: Picks a "pivot" element, partitions array elements into those smaller and larger than the pivot, and sorts partitions recursively. In-place (O(log n) stack space) and extremely fast in practice, but worst-case O(n²) if a poor pivot is picked.
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.concat(left.slice(i)).concat(right.slice(j));
}
console.log(mergeSort([38, 27, 43, 3, 9, 82, 10]));Set your Publisher ID in src/config/ads.ts to display live ads.
Test Yourself With Exercise
What is the worst-case time complexity of MergeSort on an array of length n?