Merge Sort: Divide, Sort, Merge
Implement merge sort recursively, trace the divide-and-conquer tree, and explain why it guarantees O(n log n) in all cases.
Merge Sort: Divide, Sort, Merge is a free DSA Interview Prep lesson on CoddyKit — lesson 2 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Divide and Conquer Intuition
Merge sort is a classic divide-and-conquer algorithm: split the array in half, recursively sort each half, then merge the two sorted halves into one sorted result. The insight is that merging two sorted arrays is O(n) — far cheaper than sorting from scratch. This decomposition produces a recursion tree with log n levels, each requiring O(n) merge work, giving the optimal comparison-sort bound of O(n log n).
# High-level merge sort structure
def merge_sort(arr):
# Base case: 0 or 1 element already sorted
if len(arr) <= 1:
return arr
# Divide
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # sort left half
right = merge_sort(arr[mid:]) # sort right half
# Conquer (merge)
return merge(left, right)
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
# [3, 9, 10, 27, 38, 43, 82]The Merge Step Explained
Merging two sorted arrays: maintain two pointers, one for each half. Compare the front elements; copy the smaller one to the output and advance that pointer. When one half is exhausted, copy the remainder of the other half directly. This runs in O(n) time and O(n) space for the output array. The merge step is the algorithmic heart of merge sort — understand it deeply.
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= preserves stability
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
# Append remaining elements
result.extend(left[i:])
result.extend(right[j:])
return result
print(merge([1,3,5,7], [2,4,6,8]))
# [1, 2, 3, 4, 5, 6, 7, 8]Complete Merge Sort Implementation
Putting divide and merge together: the recursive calls halve the problem until single elements remain (trivially sorted), then the merge calls combine them back. Each level of the recursion tree merges the same n elements total (distributed across multiple merges). The recursion depth is log₂(n), giving O(n log n) total time and O(n) auxiliary space for the merge output arrays plus O(log n) call-stack depth.
def merge_sort_full(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort_full(arr[:mid])
right = merge_sort_full(arr[mid:])
# Merge the two sorted halves
merged = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: merged.append(left[i]); i += 1
else: merged.append(right[j]); j += 1
merged.extend(left[i:] + right[j:])
return merged
print(merge_sort_full([5,2,4,6,1,3,2,6]))
# [1, 2, 2, 3, 4, 5, 6, 6]Merge Sort Recursion Tree
Visualise merge sort's recursion tree for n=8: Level 0 has one array of 8 elements; Level 1 has two arrays of 4; Level 2 has four of 2; Level 3 has eight single elements (base cases). Going back up, Level 3→2 merges 8 elements total, Level 2→1 merges 8 total, Level 1→0 merges 8 total. That is 3 levels × 8 elements = 24 operations ≈ 8 × log₂(8) = 24. This confirms O(n log n).
# Trace the tree depth
level_work = []
def merge_sort_traced(arr, depth=0):
if depth >= len(level_work):
level_work.append(0)
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort_traced(arr[:mid], depth+1)
right = merge_sort_traced(arr[mid:], depth+1)
level_work[depth] += len(arr) # track merge work
merged = sorted(left + right) # simplified merge
return merged
merge_sort_traced(list(range(8, 0, -1)))
for d, work in enumerate(level_work):
print(f'Level {d}: {work} elements merged')In-Place Merge Sort
The standard recursive merge sort allocates O(n) auxiliary space for merge output. An in-place merge sort exists but is complex and has high constant factors — rarely asked in interviews. The common interview follow-up is: 'Can you do merge sort in O(1) extra space?' The correct answer: 'In theory yes, but practical implementations sacrifice either O(n) space or add complexity; Python's Timsort uses O(n) space for merging.'
# Bottom-up merge sort: iterative, avoids recursion stack
def merge_sort_bottomup(arr):
n = len(arr)
width = 1
while width < n:
for i in range(0, n, 2 * width):
left = arr[i:i+width]
right = arr[i+width:i+2*width]
# Merge and put back
merged = []
a, b = 0, 0
while a < len(left) and b < len(right):
if left[a] <= right[b]: merged.append(left[a]); a+=1
else: merged.append(right[b]); b+=1
merged += left[a:] + right[b:]
arr[i:i+len(merged)] = merged
width *= 2
return arr
print(merge_sort_bottomup([5,2,4,6,1,3]))
# [1, 2, 3, 4, 5, 6]Merge Sort is Stable
Merge sort is stable: equal elements from the left half always appear before equal elements from the right half in the merged output. This is guaranteed by using <= (not <) when preferring the left element. Stability matters for multi-key sorting. Python's built-in sorted() and list.sort() use Timsort, which is also stable and O(n log n), making them the safe choice for all production code.
# Demonstrating stability: sort (value, original_index) pairs
items = [(3,'A'), (1,'B'), (3,'C'), (2,'D')]
# Sort by value only
result = merge_sort_full(items) # won't work directly
# Use Python's stable sort:
result = sorted(items, key=lambda x: x[0])
print(result)
# [(1,'B'),(2,'D'),(3,'A'),(3,'C')]
# 'A' comes before 'C' for value=3 (stable order)Merge K Sorted Arrays
Merging k sorted arrays of total n elements can be done by repeatedly merging pairs (like a tournament bracket), taking O(n log k) time. Each merge level processes n elements, and there are log k levels. Alternatively, use a min-heap of size k: push the smallest remaining element from each array, pop the minimum, push the next from that array. Heap approach is also O(n log k) but more memory-efficient for k that is very large.
import heapq
def merge_k_sorted(arrays):
result = []
heap = []
# Push first element from each array with array index
for i, arr in enumerate(arrays):
if arr:
heapq.heappush(heap, (arr[0], i, 0))
while heap:
val, arr_i, elem_i = heapq.heappop(heap)
result.append(val)
if elem_i + 1 < len(arrays[arr_i]):
next_val = arrays[arr_i][elem_i + 1]
heapq.heappush(heap, (next_val, arr_i, elem_i+1))
return result
arrs = [[1,4,7],[2,5,8],[3,6,9]]
print(merge_k_sorted(arrs)) # [1,2,3,4,5,6,7,8,9]Count Inversions with Merge Sort
Counting inversions (pairs where a[i] > a[j] and i < j) in O(n log n) uses a modified merge sort. During the merge step, when an element from the right subarray is smaller than an element from the left subarray, it forms an inversion with every remaining element in the left subarray. Add len(left) - i to the count at that moment.
def count_inversions(arr):
if len(arr) <= 1:
return arr, 0
mid = len(arr) // 2
left, l_inv = count_inversions(arr[:mid])
right, r_inv = count_inversions(arr[mid:])
merged = []
inversions = l_inv + r_inv
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i]); i += 1
else:
merged.append(right[j]); j += 1
inversions += len(left) - i # all remaining left elements > right[j]
merged.extend(left[i:] + right[j:])
return merged, inversions
_, inv = count_inversions([3, 1, 2])
print(inv) # 2: (3,1) and (3,2)Merge Sort vs Quick Sort
Merge sort guarantees O(n log n) in all cases, is stable, and is the better choice for linked lists and external sorting. Quick sort has O(n log n) average case but O(n²) worst case, is in-place (O(log n) stack space), and is often faster in practice due to cache efficiency on arrays. Python's built-in sort uses Timsort (merge sort variant) — always the right default choice.
# Head-to-head complexity comparison:
# Algorithm | Best | Avg | Worst | Space | Stable
# Bubble sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes
# Insertion sort| O(n) | O(n^2) | O(n^2) | O(1) | Yes
# Merge sort | O(nlogn)| O(nlogn)| O(nlogn)| O(n) | Yes
# Quick sort | O(nlogn)| O(nlogn)| O(n^2) | O(logn)| No
# Heap sort | O(nlogn)| O(nlogn)| O(nlogn)| O(1) | No
print('Merge sort: stable, O(n log n) guaranteed, O(n) space')External Sort: Merge Sort at Scale
Merge sort is the algorithm behind external sorting (sorting data too large to fit in RAM). Data is read in chunks, each chunk sorted in memory, and chunks are merged from disk. The merge step reads one element at a time from each sorted run, keeping only O(k) elements in memory at once (one per run). This is why merge sort is used in databases, Hadoop MapReduce, and classic tape-sort algorithms.
# Simulated external sort: sort in chunks then merge
def external_sort(data, chunk_size):
chunks = []
for i in range(0, len(data), chunk_size):
chunk = sorted(data[i:i+chunk_size]) # sort in-memory
chunks.append(chunk)
print(f'Created {len(chunks)} sorted chunks')
# Merge all chunks
import heapq
heap = [(c[0], i, 0) for i, c in enumerate(chunks) if c]
heapq.heapify(heap)
result = []
while heap:
val, ci, ei = heapq.heappop(heap)
result.append(val)
if ei + 1 < len(chunks[ci]):
heapq.heappush(heap, (chunks[ci][ei+1], ci, ei+1))
return result
print(external_sort(list(range(20,0,-1)), 5)[:10])Merge Sort Summary and Interview Tips
In interviews, implementing merge sort cleanly demonstrates understanding of recursion, the merge step, and divide-and-conquer. Common follow-ups:
- Why O(n log n) and not O(n²)? (log n levels × n work per level)
- Is it stable? (Yes, use <= in the merge)
- How much space? (O(n) auxiliary + O(log n) stack)
- Can you do it iteratively? (Yes, bottom-up merge sort)
- How would you use it on a linked list? (Easier than on array — no O(n) slice cost; use slow-fast to find midpoint)
# One-shot merge sort for interview clarity:
def ms(a):
if len(a) <= 1: return a
m = len(a) // 2
l, r, res, i, j = ms(a[:m]), ms(a[m:]), [], 0, 0
while i < len(l) and j < len(r):
if l[i] <= r[j]: res.append(l[i]); i+=1
else: res.append(r[j]); j+=1
return res + l[i:] + r[j:]
print(ms([5,2,4,6,1,3])) # [1,2,3,4,5,6]Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: merge sort splits the array at the midpoint, recursively sorts each half, and merges the two sorted halves in O(n) — producing an O(n log n) total runtime across log n recursion levels, the merge step uses <= to take the left element on ties, guaranteeing stability, and merge sort is the algorithm of choice for linked lists, external sorting, and when stability is required — while quick sort is preferred for in-memory arrays when space is limited. Next up we implement quick sort and explore pivot selection strategies.
Frequently asked questions
Is the “Merge Sort: Divide, Sort, Merge” lesson free?
Yes — the full text of “Merge Sort: Divide, Sort, Merge” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Merge Sort: Divide, Sort, Merge”?
Implement merge sort recursively, trace the divide-and-conquer tree, and explain why it guarantees O(n log n) in all cases. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 2 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Merge Sort: Divide, Sort, Merge” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Bubble Sort and Insertion Sort
- Merge Sort: Divide, Sort, Merge
- Quick Sort and Pivot Selection
- Non-Comparison Sorts and Python's sort()