Merge sort splits the array in half recursively until each piece is a single element (which is trivially sorted), then merges those pieces back together in sorted order. The merge step walks both halves simultaneously and always picks the smaller element. Because the work is split log n ways and each level does O(n) merge work, the total is O(n log n) — faster than the quadratic sorts and guaranteed regardless of input order.
Example: Sort 6 numbers using divide and conquer.
When to use this
→General-purpose stable sort — guaranteed O(n log n) on all inputs
→Sorting linked lists — merge sort works naturally without random access
→External sorting — merging sorted chunks from disk when data doesn't fit in RAM
→Count inversions in an array (modified merge step)
→Sort large datasets where worst-case guarantees matter (unlike quick sort)
Merge sort divides the array in half recursively until each piece is a single element, then merges those pieces back in sorted order. Dividing costs nothing; the real work happens during the merge.
Space play/pause← → stepR replay+ − speed
active line highlighted
1
defmerge_sort(arr):
2
iflen(arr)<=1:
3
returnarr
4
mid=len(arr)//2
5
left=merge_sort(arr[:mid])
6
right=merge_sort(arr[mid:])
7
result=[]
8
i=j=0
9
whilei<len(left)andj<len(right):
10
ifleft[i]<=right[j]:
11
result.append(left[i]);i+=1
12
else:
13
result.append(right[j]);j+=1
14
returnresult+left[i:]+right[j:]
Quick check
Why is merge sort O(n log n) instead of O(n²)?
What extra cost does merge sort have compared to bubble or selection sort?