Introduction
Merge sort is one of the clearest illustrations of the divide-and-conquer paradigm applied to sorting. It repeatedly splits an array in half until each piece contains a single element, then merges those pieces back together in sorted order. Unlike quicksort, merge sort's worst-case performance is guaranteed to be O(n log n), which makes it a reliable choice when predictable performance matters, such as in external sorting or stable sorting requirements.
Cricket analogy: Merge sort is like ranking every player in a huge tournament by repeatedly splitting the field into halves until each group has one player, then merging ranked pairs back together; unlike a knockout bracket (quicksort) that can go badly if seeded unluckily, this method guarantees a reliable O(n log n) ranking every time.
Algorithm/Syntax
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
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
result.extend(left[i:])
result.extend(right[j:])
return resultExplanation
The divide step splits the array at its midpoint into two halves. The conquer step recursively sorts each half; the recursion bottoms out at arrays of length 0 or 1, which are trivially sorted. The combine step, implemented by the merge function, walks through both sorted halves simultaneously, always picking the smaller of the two front elements, until one half is exhausted, then appends the remainder of the other half. Because merging two sorted lists of total length n takes O(n) time, and the array is split in half at each recursive level, merge sort performs the same amount of merge work at every one of the O(log n) levels of recursion.
Cricket analogy: Splitting a squad list at its midpoint, recursively ranking each half down to a single player (trivially 'sorted'), then merging by always picking whichever front player has the better average is merge sort's structure; the merge step touches every player once per level, across O(log n) levels of splitting.
Example
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
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
result.extend(left[i:])
result.extend(right[j:])
return result
# Trace: [38, 27, 43, 3, 9, 82, 10]
# Split -> [38, 27, 43] and [3, 9, 82, 10]
# Recurse until singletons, then merge back up:
# [38] + [27] -> [27, 38]
# [27, 38] + [43] -> [27, 38, 43]
# [3] + [9] -> [3, 9]; [82] + [10] -> [10, 82]
# [3, 9] + [10, 82] -> [3, 9, 10, 82]
# [27, 38, 43] + [3, 9, 10, 82] -> final sorted array
nums = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(nums)) # [3, 9, 10, 27, 38, 43, 82]Complexity
Merge sort's recurrence is T(n) = 2T(n/2) + O(n), which the master theorem resolves to O(n log n) in the best, average, and worst cases -- there is no input ordering that causes it to degrade, unlike quicksort. Its space complexity is O(n) because the merge step needs auxiliary arrays to hold the merged output, and it is a stable sort, meaning equal elements retain their relative order, which matters for multi-key sorting.
Cricket analogy: Merge sort's recurrence T(n)=2T(n/2)+O(n) resolves via the master theorem to O(n log n) no matter the starting order of the squad list, unlike a fragile ranking method that could degrade on an already-sorted team sheet; it needs extra O(n) scratch space, and stability preserves tie order, keeping equal averages in original entry order for a secondary sort by strike rate.
Key Takeaways
- Merge sort divides the array in half recursively until reaching single-element base cases, then merges sorted halves back together.
- The merge step is the combine phase and runs in O(n) time for each level of recursion.
- Merge sort guarantees O(n log n) time in all cases, unlike quicksort's O(n^2) worst case.
- Merge sort uses O(n) extra space and is stable, preserving the relative order of equal elements.
Practice what you learned
1. What is the time complexity of merge sort in the worst case?
2. What is the primary role of the merge function in merge sort?
3. Why is merge sort considered a stable sorting algorithm?
4. What is the auxiliary space complexity of the standard merge sort implementation?
Was this page helpful?
You May Also Like
The Divide and Conquer Paradigm
Learn how divide, conquer, and combine steps break large problems into smaller solvable subproblems.
The Master Theorem
Apply the Master Theorem's three cases to quickly solve divide-and-conquer recurrences of the form T(n) = aT(n/b) + f(n).
The Quickselect Algorithm
Find the k-th smallest element in linear average time using a partition-based divide-and-conquer approach.
Recursion Trees and Recurrence Relations
Model the runtime of recursive algorithms as recurrence relations and solve them by drawing recursion trees.