DSA — Sorting Algorithms

Merge Sort

Divide array in half recursively, sort each half, then merge. Classic divide-and-conquer with guaranteed O(n log n).

— min read
O(n log n)All Cases
O(n)Space
Divide& Conquer
StableSort
✓Linked Lists
// MERGE SORT — LIVE ANIMATION
Speed
Press ▶ Sort to begin
How It Works
Python Code
Complexity
Quiz
Practice
01
Divide
Split array at midpoint into two halves.
mid = len(arr) // 2
02
Conquer
Recursively sort left and right halves.
merge_sort(left), merge_sort(right)
03
Merge
Merge two sorted halves by comparing front elements.
while i < len(L) and j < len(R)
04
Stable
Left subarray wins ties — relative order preserved.
if L[i] <= R[j]: use L[i]
python 
def merge_sort(arr):
    if len(arr) <= 1: return arr
    mid = len(arr) // 2
    L = merge_sort(arr[:mid])
    R = merge_sort(arr[mid:])
    return merge(L, R)

def merge(L, R):
    res, i, j = [], 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:]
O(n log n)
Always
Guaranteed — log n levels × n per level
O(n)
Extra Space
Temporary arrays during merge phase
Stable
Equal elements
Left wins ties — order preserved
Best For
Linked Lists
No random access needed for merging
Why does Merge Sort use O(n) extra space?
Progress 0 / 6 solved
6 problems · 4 PBC · 2 Startup
#1751 Sort List Google, Amazon PBC →
#1752 Merge Sorted Array Meta, Microsoft PBC →
#1753 Merge K Sorted Lists Google, Amazon PBC →
#1754 Count of Smaller Numbers After Self Google PBC →
#1755 Count Inversions in Array Flipkart STARTUP →
#1756 Reverse Pairs Zepto STARTUP →
← Insertion Sort