Chapter 8: DSA Merge Sort
DSA Merge Sort – Let’s learn this one properly, like I’m sitting next to you with a whiteboard, explaining slowly, step-by-step, with clear examples, visuals in words, code, and most importantly — why people actually use it and when it beats other algorithms.
What is Merge Sort?
Merge Sort is a classic divide-and-conquer sorting algorithm.
Its core idea is very elegant and powerful:
Divide the array into two halves → recursively sort both halves → then merge the two sorted halves into one sorted array.
It’s called Merge Sort because the most important (and clever) part is the merge step — combining two already sorted arrays into one sorted array very efficiently.
Merge Sort – The Three Main Steps
- Divide Split the array into two roughly equal parts (left and right half).
- Conquer Recursively sort the left half and recursively sort the right half.
- Combine (Merge) Merge the two sorted halves into a single sorted array.
The recursion keeps dividing until we reach arrays of size 1 (which are already sorted), then we start merging back up.
Visual Example – Step by Step
Array: [38, 27, 43, 3, 9, 82, 10]
|
0 1 2 3 4 5 6 7 8 9 10 11 12 |
[38, 27, 43, 3, 9, 82, 10] / \ [38, 27, 43] [3, 9, 82, 10] / \ / \ [38, 27] [43] [3, 9] [82, 10] / \ / \ / \ [38] [27] [3] [9] [82] [10] |
Now we start merging from the bottom up:
Level 1 – Merge single elements
- [38] + [27] → [27, 38]
- [3] + [9] → [3, 9]
- [82] + [10] → [10, 82]
Level 2 – Merge pairs
- [27, 38] + [43] → [27, 38, 43]
- [3, 9] + [10, 82] → [3, 9, 10, 82]
Level 3 – Final merge
- [27, 38, 43] + [3, 9, 10, 82] → [3, 9, 10, 27, 38, 43, 82]
Done!
The Merge Step – Very Important (this is where the magic happens)
Merge two sorted arrays — this operation is linear time O(n).
How it works:
You have two sorted arrays:
Left: [27, 38, 43] Right: [3, 9, 10, 82]
You use two pointers (i for left, j for right) and build a new result array.
- Compare left[i] and right[j]
- Take the smaller one → put it in result
- Move the pointer of the array from which you took
- Repeat until one array is exhausted
- Copy remaining elements of the other array
Step-by-step merge:
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
Left: 27 38 43 Right: 3 9 10 82 Compare 27 vs 3 → take 3 → result = [3] Compare 27 vs 9 → take 9 → result = [3, 9] Compare 27 vs 10 → take 10 → result = [3, 9, 10] Compare 27 vs 82 → take 27 → result = [3, 9, 10, 27] Compare 38 vs 82 → take 38 → result = [3, 9, 10, 27, 38] Compare 43 vs 82 → take 43 → result = [3, 9, 10, 27, 38, 43] Left finished → copy remaining right → [3, 9, 10, 27, 38, 43, 82] |
Merge Sort Code – Most Common Interview Version (Python)
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
def merge_sort(arr): if len(arr) <= 1: return arr # Divide mid = len(arr) // 2 left = merge_sort(arr[:mid]) right = merge_sort(arr[mid:]) # Conquer + Combine return merge(left, right) def merge(left, right): result = [] i = j = 0 # Compare and merge while i < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 # Add remaining elements result.extend(left[i:]) result.extend(right[j:]) return result # Example numbers = [38, 27, 43, 3, 9, 82, 10] print("Before:", numbers) sorted_numbers = merge_sort(numbers) print("After: ", sorted_numbers) # Output: [3, 9, 10, 27, 38, 43, 82] |
In-place Merge Sort (sometimes asked in interviews)
The version above uses extra space O(n). There is an in-place version that tries to use O(1) extra space — but it’s more complicated and slower in practice.
Most companies accept the O(n) space version — it’s cleaner and easier to implement correctly.
Time & Space Complexity (must know perfectly)
| Case | Time Complexity | Explanation |
|---|---|---|
| Best Case | O(n log n) | Always divides and merges |
| Average Case | O(n log n) | |
| Worst Case | O(n log n) | No bad case like QuickSort |
| Space Complexity | O(n) | Needs temporary array for merging (can be O(log n) with clever tricks) |
Number of comparisons ≈ n log n – n + 1 (very predictable)
Merge Sort vs Quick Sort – Interview Comparison (very common question)
| Feature | Merge Sort | Quick Sort |
|---|---|---|
| Time (average) | O(n log n) | O(n log n) |
| Time (worst) | O(n log n) | O(n²) |
| Space | O(n) | O(log n) average |
| In-place? | No (usually) | Yes |
| Stable? | Yes | No |
| Best for | Stability, linked lists | General arrays, cache-friendly |
| Worst-case behavior | Predictable | Can be very bad (sorted array + bad pivot) |
| Real-world usage | External sorting, stability | Most language built-ins |
When is Merge Sort actually used?
Real-world usage is very common (unlike Bubble/Selection/Insertion):
- Stability is required (same values keep original relative order)
- Sorting linked lists (very efficient — O(1) extra space possible)
- External sorting (sorting huge files that don’t fit in RAM)
- TimSort hybrid (Python, Java, Android) uses Merge Sort ideas
- When worst-case guarantee is important
- Parallel sorting (easy to parallelize divide step)
Summary – Merge Sort in one line each
- Classic divide-and-conquer sorting algorithm
- Divides array into halves → recursively sorts them → merges sorted halves
- Always O(n log n) — no bad worst case
- Stable sorting
- Uses O(n) extra space (temporary arrays for merging)
- Merge step is the heart of the algorithm — linear time combination of two sorted arrays
- Very reliable, predictable, widely used when stability or guaranteed performance matters
Would you like to continue with any of these next topics?
- How to implement in-place merge sort
- Merge Sort on linked lists (very common interview variation)
- Bottom-up Merge Sort (iterative version)
- Common interview questions on Merge Sort
- Merge Sort vs Quick Sort vs Heap Sort detailed comparison
- How TimSort combines Merge Sort + Insertion Sort
Just tell me which direction you want — I’ll explain it in the same detailed, friendly style! 😊
