Merge Sort & Quick Sort

Divide and conquer, the strategy behind the fastest general-purpose sorts

Divide and conquer splits a problem into smaller subproblems, solves each recursively, then combines results. Merge sort is the canonical example.
Merge Sort:1. Split array in half2. Recursively sort each half3. Merge the two sorted halves
Guaranteed O(n log n), no bad worst cases (unlike quicksort's O(n²) worst case).

Merge sort implementationpython

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)       # Merge sorted halves

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

print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
# → [3, 9, 10, 27, 38, 43, 82]

Merge Sort is stable, equal elements keep their original order. Quick Sort is not by default. Stability matters when sorting complex objects (e.g., sort by last name, then by first name, you need stability for the first sort to be preserved).

🤔Quick Check

What is the space complexity of merge sort?

🎯

Phase Complete!

Search & Sort

You can implement binary search, understand common sorting algorithms, and know their trade-offs. Recursion is next, the foundation for trees, graphs, and DP.

0/500

Practice Exercises

0/1 solved

Exercise 1 of 1hard

⏱ 00:00

Count Inversions

Count how many pairs (i, j) exist where i < j but arr[i] > arr[j]. Use merge sort to do it in O(n log n).
Expected output: 3
(Pairs: (3,1), (3,2), (5,2) in [3,1,2,5,4], wait, that's [5,4]. Let's use [3,1,2].)

solution.py

1 / 1

Solve all 1 exercise to unlock completion

Previous Next