Beginner LevelData Structures & Algorithms
How does Merge Sort work and why is it preferred for stable sorting?
ā Interview Prompt: Explain Merge Sort, divide and conquer paradigm, O(N log N) time complexity, O(N) auxiliary space, stability, and external sorting use cases.
Merge Sort is a divide-and-conquer sorting algorithm:
1
Divide: Split array into two halves recursively until each sub-array has 1 element.
2
Conquer: Merge adjacent sorted sub-arrays back together in sorted order.
Complexity:
ā¢
Time: $O(N \log N)$ at all cases (best, average, worst).
ā¢
Space: $O(N)$ auxiliary space for the merge step.
ā¢
Stable: Equal elements preserve their relative input order.
When to Use:
ā¢
Sorting linked lists (preferred over Quicksort ā no random access needed).
ā¢
External sorting of data too large for RAM (merge sorted file chunks).
ā¢
Any scenario requiring stable sort with guaranteed $O(N \log N)$.
Code Implementation Example
typescript
function mergeSort(arr: number[]): number[] {
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: number[], right: number[]): number[] {
const result: number[] = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
result.push(left[i] <= right[j] ? left[i++] : right[j++]);
}
return [...result, ...left.slice(i), ...right.slice(j)];
}š”Merge Sort: divide-and-conquer producing sorted output in O(N log N).
šÆ Interview Key Takeaway
Merge Sort guarantees O(N log N) for all cases with O(N) space. Prefer it for linked lists and when stability matters.
#DSA#Merge Sort#Sorting#Divide and Conquer#Beginner
Back to all Data Structures & Algorithms Questionsā