DSA · Lesson 11 of 20 · 4 min
Sorting Algorithms II: Divide & Conquer
This is how you explain the trade-offs between the two most common O(n log n) sorting algorithms in an interview.
After the O(n²) sorts, we get to the ones you'll actually be asked to implement and analyze: Merge Sort and Quick Sort. They both use a "divide and conquer" strategy, but their performance characteristics are opposites. Knowing which to use, and why, is the entire point.
Merge Sort: Stable and predictable
Merge Sort divides an array in half, recursively sorts each half, and then merges the two sorted halves back together. Its performance is consistent, which is its main selling point.
The work happens in the merge step. You have two sorted arrays, and you create a new one by walking through both, picking the smaller element at each step, until you've exhausted both inputs.
The trade-offs
Merge Sort's time complexity is O(n log n) in all cases—best, average, and worst. This predictability is valuable. If you're sorting data for a UI render that has to happen in under 16ms, you can't afford a surprise O(n²) hiccup.
It's also a stable sort. If two elements are considered equal, their original relative order is preserved. This is critical if you're sorting a list of objects by one property, then another. For example, sorting users by last name, where users with the same last name should remain in their original order.
The major downside is space. A standard implementation requires O(n) auxiliary space to hold the merged arrays. This can be a deal-breaker for very large datasets in memory-constrained environments.
The code
This implementation shows the classic out-of-place merge. Note how the merge function does the heavy lifting.
function mergeSort<T>(arr: T[]): T[] {
if (arr.length <= 1) {
return arr;
}
const mid = Math.floor(arr.length / 2);
const left = arr.slice(0, mid);
const right = arr.slice(mid);
return merge(mergeSort(left), mergeSort(right));
}
function merge<T>(left: T[], right: T[]): T[] {
const result: T[] = [];
let leftIndex = 0;
let rightIndex = 0;
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] < right[rightIndex]) {
result.push(left[leftIndex]);
leftIndex++;
} else {
result.push(right[rightIndex]);
rightIndex++;
}
}
// Append remaining elements from either left or right
return result
.concat(left.slice(leftIndex))
.concat(right.slice(rightIndex));
}
Quick Sort: Fast, but with a weak spot
Quick Sort also divides the work, but differently. It picks an element (the "pivot"), and partitions the array so that all elements smaller than the pivot come before it, and all elements larger come after. The pivot is now in its final sorted position. Then it recursively sorts the sub-arrays to the left and right of the pivot.
Unlike Merge Sort, there's no separate "combine" step. The work is done up-front in the partitioning.
The trade-offs
Quick Sort's average time complexity is O(n log n) and it's often faster in practice than Merge Sort. This is because it has better cache locality and the partitioning can be done in-place, without allocating new arrays.
Its space complexity is O(log n) on average, for the recursion call stack. This is a huge advantage over Merge Sort's O(n).
The trap: The pivot is everything. If you consistently pick a bad pivot (like the smallest or largest element), the partitions become extremely unbalanced. In the worst case, you're just splitting off one element at a time, which degrades the time complexity to O(n²). A sorted array is a classic trigger for this worst-case behavior if you always pick the last element as the pivot.
Quick Sort is also not stable. The partitioning process shuffles equal elements around, so their original order is not guaranteed.
The code
This implementation sorts in-place, modifying the input array directly. The partition function rearranges a sub-array and returns the final index of the pivot.
function quickSort<T>(arr: T[], low: number = 0, high: number = arr.length - 1): void {
if (low < high) {
const pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
function partition<T>(arr: T[], low: number, high: number): number {
const pivot = arr[high];
let i = low - 1;
for (let j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]]; // Swap
}
}
[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]]; // Place pivot
return i + 1;
}
How to answer "Merge Sort vs. Quick Sort"
This is a classic question. Don't just list complexities. Show you understand the practical implications.
Your answer should cover these points:
- Memory: Is the dataset huge? Quick Sort's O(log n) space is a clear winner over Merge Sort's O(n) if memory is a concern.
- Stability: Do you need to preserve the order of equal elements? Use Merge Sort. Quick Sort is not stable.
- Predictability: Do you need a performance guarantee? Merge Sort's worst case is the same as its average case, O(n log n). Quick Sort's O(n²) worst case, while rare with good pivot selection, can be a risk.
- Context: For a frontend developer, it's impressive to know that browser engines often use hybrid algorithms. V8's
Array.prototype.sortuses Timsort (a hybrid of Merge Sort and Insertion Sort) for performance, stability, and memory efficiency.
The trap: A candidate says "Quick Sort is faster." A senior engineer says "Quick Sort is often faster in practice for generic data due to its in-place nature and cache efficiency, but its O(n²) worst-case makes it unsuitable for applications requiring guaranteed performance, where Merge Sort would be a safer choice."
Try it
Implement quickSort, but modify the partition function to use a random element as the pivot instead of the last one. This is a simple way to make the worst-case O(n²) performance extremely unlikely in practice.
Next: We'll see how sorted data enables much faster lookups in Searching Algorithms: Linear & Binary Search.
Lock it in — apply this lesson under interview conditions.