Merge sort is a divide-and-conquer, stable sort that runs in guaranteed O(n log n) time. It splits the array in half, sorts each half recursively, then merges the two sorted halves.
A single element is already sorted (base case). Merging two sorted lists is linear, and we do log n levels of merging.
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # sort left half
right = merge_sort(arr[mid:]) # sort right half
return merge(left, right)
def merge(a, b):
result, i, j = [], 0, 0
while i < len(a) and j < len(b):
if a[i] <= b[j]: # <= keeps it stable
result.append(a[i]); i += 1
else:
result.append(b[j]); j += 1
result.extend(a[i:]); result.extend(b[j:])
return result
merge_sort([5, 2, 4, 1, 3]) # -> [1, 2, 3, 4, 5]
Ideal when you need stability or guaranteed O(n log n), and for linked lists and external sorting of huge files. The extra O(n) memory is its main drawback.
Merge sort guarantees O(n log n) regardless of input, unlike quicksort's O(n²) worst case.
Its stability preserves the relative order of equal keys, which matters for multi-key sorting.
The merge step is a reusable primitive, and the divide-and-conquer structure is a template you will reuse everywhere.
A library of IT interview questions with detailed answers — from Junior to Senior.
Donate