Merge Sort: Divide-and-Conquer Paradigm & Stability Analysis0%
Quick Sort: Lomuto vs Hoare Partitioning & Pivot Strategies

Merge Sort: Divide-and-Conquer Paradigm & Stability Analysis

Beginner12 min read•Updated: Jul 11, 2026
Study MaterialsCheatsheet

Merge Sort: Divide-and-Conquer Paradigm & Stability Analysis

Merge Sort is an optimal, comparison-based sorting algorithm based on the Divide-and-Conquer design paradigm. It provides a guaranteed worst-case, average-case, and best-case time complexity of $O(n \log n)$ while maintaining strict stability.

1. Real-World Analogy: Sorting Two Piles of Graded Exam Papers

Imagine two teaching assistants have each sorted a stack of 50 student exam papers alphabetically:

  • Stack A: 50 sorted papers (Aarav, Ananya, David ...)
  • Stack B: 50 sorted papers (Ben, Chris, Emily ...)
  • To merge them into a single 100-paper sorted stack, you don't start from scratch!
  • You look at the top sheet of Stack A and top sheet of Stack B: compare Aarav with Ben. Aarav comes first $\to$ place in final pile.
  • Repeat. In a single pass of 100 quick comparisons, the entire stack is perfectly merged!

2. The Divide-and-Conquer Triad

  1. 1
    Divide: Split the array at midpoint $\text{mid} = \frac{\text{low} + \text{high}}{2}$ into two equal halves until subarrays contain $\le 1$ element (the base case).
  2. 2
    Conquer: Recursively sort both the left half and right half.
  3. 3
    Combine (Merge): Merge the two sorted subarrays back together into a single sorted array.
Output
Recursion Tree for Merge Sort on [38, 27, 43, 3, 9, 82, 10]:
Level 0: [38, 27, 43, 3, 9, 82, 10]
Level 1: [38, 27, 43] [3, 9, 82, 10]
Level 2: [38] [27, 43] [3, 9] [82, 10]
Level 3: [38] [27] [43] [3] [9] [82] [10]
------------------------ MERGING PHASE ------------------------
Level 2: [38] [27, 43] [3, 9] [10, 82]
Level 1: [27, 38, 43] [3, 9, 10, 82]
Level 0: [3, 9, 10, 27, 38, 43, 82] (SORTED!)

3. The Recurrence Relation & Master Theorem Proof

$$\text{Time Complexity: } T(n) = 2 T\left(\frac{n}{2}\right) + O(n)$$

  • The tree has $\log_2(n)$ levels.
  • At each level, merging all elements takes total $O(n)$ work.
  • Total Time: $\log_2(n) \times O(n) = \mathbf{O(n \log n)}$.

4. Multi-Language Implementations: Merge Sort

Python 3 Implementation:

Python
def merge_sort(arr: list[int]) -> list[int]:
if len(arr) <= 1:
return arr
mid = len(arr) // 2
# 1. Divide & Conquer
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
# 2. Combine (Merge)
return merge(left, right)
 
def merge(left: list[int], right: list[int]) -> list[int]:
merged = []
i = j = 0
# Two-pointer zip merge
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= preserves STABILITY!
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
merged.extend(left[i:])
merged.extend(right[j:])
return merged

Modern JavaScript / TypeScript (In-Place Indices):

TypeScript
export function mergeSort(arr: number[], low: number = 0, high: number = arr.length - 1): void {
if (low >= high) return;
 
const mid = low + Math.floor((high - low) / 2);
mergeSort(arr, low, mid);
mergeSort(arr, mid + 1, high);
merge(arr, low, mid, high);
}
 
function merge(arr: number[], low: number, mid: number, high: number): void {
const temp: number[] = [];
let i = low;
let j = mid + 1;
 
while (i <= mid && j <= high) {
if (arr[i] <= arr[j]) {
temp.push(arr[i++]);
} else {
temp.push(arr[j++]);
}
}
 
while (i <= mid) temp.push(arr[i++]);
while (j <= high) temp.push(arr[j++]);
 
for (let k = 0; k < temp.length; k++) {
arr[low + k] = temp[k];
}
}

5. Trace Table: Merging Left [27, 38] and Right [9, 43]

Stepleft[i]right[j]Comparison (left[i] <= right[j])Appended to mergedRemaining
1279$27 \le 9$ (False)[9]j advances to 1
22743$27 \le 43$ (True)[9, 27]i advances to 1
33843$38 \le 43$ (True)[9, 27, 38]i exhausted
4-43Remaining right elements[9, 27, 38, 43]Complete!
Interactive Quiz

Multiple Choice Questions

Question 1
What is the guaranteed worst-case time complexity of Merge Sort?
Question 2
How much auxiliary memory does standard Merge Sort on an array of size $n$ consume during the merge phase?
Question 3
Why is Merge Sort the preferred sorting algorithm for Singly Linked Lists over Quick Sort?
Question 4
Which comparison operator in the merge function guarantees that Merge Sort remains "Stable"?
Question 5
How many total recursive levels are present in the Merge Sort recursion tree for an input of size $n$?
Next Lesson

Quick Sort: Lomuto vs Hoare Partitioning & Pivot Strategies

Continue learning with hands-on practice, examples, and exercises in the upcoming topic.

Related Lessons

Previous LessonNext Lesson
Elementary Sorting Algorithms: Bubble, Selection & Insertion Sort (O(n²))Quick Sort: Lomuto vs Hoare Partitioning & Pivot Strategies

Practice Quiz

Test your understanding of this lesson with 5 questions. Each question has one correct answer.

PreviousNext
PrevNext