DSA — Merge Sort

What is Merge Sort?

Divides the array into halves, recursively sorts them, then merges.

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

How it Works

[38, 27, 43, 3, 9, 82, 10]
        ↓
[38, 27, 43, 3] [9, 82, 10]
    ↓           ↓
[38, 27] [43, 3] [9, 82] [10]
  ↓       ↓       ↓      ↓
[27, 38] [3, 43] [9, 82] [10]
    ↓           ↓
[3, 27, 38, 43] [9, 10, 82]
        ↓
[3, 9, 10, 27, 38, 43, 82]

Time Complexity

Case	Complexity
Best	O(n log n)
Average	O(n log n)
Worst	O(n log n)

Characteristics

• Stable sort
• Not in-place
• Predictable performance
• Good for large datasets

Mini Practice

1. Implement merge sort
2. Sort strings
3. Count inversions
4. External sort for large files

Up Next

Continue with Quick Sort — efficient divide and conquer sort.