DSA Merge Sort

DSA Tutorial

 DSA Merge Sort – Complete Beginner Guide

(Concept • Manual Run-Through • Algorithm • Code • Time Complexity)

Merge Sort is a Divide and Conquer sorting algorithm.
It divides the array into smaller parts, sorts them recursively, and then merges the sorted parts.

1️⃣ What is Merge Sort?

Merge Sort works in two phases:

  1. Divide the array into halves until each sub-array has one element

  2. Merge the sub-arrays back together in sorted order

📌 Arrays of size 1 are already sorted.

2️⃣ Simple Idea (One Line)

Divide the array → sort sub-arrays → merge them in order

3️⃣ When to Use Merge Sort?

✔ Large datasets
✔ When stable sorting is required
✔ When guaranteed O(n log n) performance is needed

❌ When memory is very limited (uses extra space)

4️⃣ Merge Sort – Manual Run-Through

 Given Array

[38, 27, 43, 3, 9, 82, 10]

 Step-1: Divide

[38, 27, 43, 3] [9, 82, 10]

 Step-2: Divide Further

[38, 27] [43, 3] [9, 82] [10]

 Step-3: Divide to Single Elements

[38] [27] [43] [3] [9] [82] [10]

 Step-4: Merge (Sorted)

[27, 38] [3, 43] [9, 82] [10]

 Step-5: Merge Again

[3, 27, 38, 43] [9, 10, 82]

 Step-6: Final Merge

[3, 9, 10, 27, 38, 43, 82]

 Final Sorted Array

[3, 9, 10, 27, 38, 43, 82]

5️⃣ Merge Sort Algorithm (Steps)

  1. If array size ≤ 1, return

  2. Find the middle of the array

  3. Recursively sort left half

  4. Recursively sort right half

  5. Merge both sorted halves

6️⃣ Merge Procedure (Key Logic)

  • Compare elements from both halves

  • Pick smaller element

  • Continue until one half is exhausted

  • Copy remaining elements

7️⃣ Pseudocode

mergeSort(arr):
if length(arr) <= 1:
return arrmid = length(arr) / 2
left = mergeSort(arr[0..mid-1])
right = mergeSort(arr[mid..end])return merge(left, right)

8️⃣ Merge Sort Implementation (C++)


 

Output

3 9 10 27 38 43 82

9️⃣ Time Complexity of Merge Sort

Merge Sort always splits the array in half.

⏱ Time Complexity Table

Case Time Complexity
Best Case O(n log n)
Average Case O(n log n)
Worst Case O(n log n)

📌 Unlike Quick Sort, worst case is also O(n log n).

🔟 Space Complexity

Metric Value
Extra Space O(n)
Reason Temporary arrays during merge

1️⃣1️⃣ Advantages of Merge Sort

✔ Guaranteed O(n log n)
✔ Stable sorting algorithm
✔ Works well for linked lists
✔ Good for large datasets

1️⃣2️⃣ Disadvantages of Merge Sort

❌ Requires extra memory
❌ Not in-place
❌ Slower than Quick Sort in practice (due to memory overhead)

1️⃣3️⃣ Merge Sort vs Quick Sort

Feature Merge Sort Quick Sort
Worst Case O(n log n) O(n²)
Stability ✅ Yes ❌ No
Space O(n) O(log n)
Speed (Avg) ⭐⭐⭐ ⭐⭐⭐⭐

 Exam / Interview Questions (Merge Sort)

Q1. Why is Merge Sort stable?
👉 Equal elements maintain order

Q2. Why Merge Sort needs extra space?
👉 Temporary arrays for merging

Q3. Which is better: Merge or Quick Sort?
👉 Depends on use case

 Final Summary

✔ Merge Sort uses divide & conquer
✔ Always O(n log n)
✔ Stable sorting algorithm
✔ Needs extra memory
✔ Very important for exams & interviews

You may also like...