Sorting & Searching Intermediate¶

🧮 Algorithms · Level 3

⏱️ ~4 days

When you'd use this

Comparison sorts, binary search, merge sort, quick sort and complexity analysis.

Sort and search efficiently, and know when to lean on Python's built-ins versus a custom approach — a staple of interviews and performance work.

Binary search — O(log n)¶

Find an item in a sorted sequence by repeatedly halving the search range.

def binary_search(arr: list[int], target: int) -> int:
    """Find target in sorted array. Returns index or -1."""
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

# Usage
arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
print(binary_search(arr, 7))    # 3 (index)
print(binary_search(arr, 8))    # -1 (not found)
# Searches 1 million items in ~20 comparisons!

Merge sort — O(n log n), stable¶

Divide-and-conquer sort that's stable and predictable — good when stability matters.

def merge_sort(arr: list) -> list:
    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: list, right: list) -> list:
    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
    return result + left[i:] + right[j:]

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

Quick sort — O(n log n) average, in-place¶

Fast in-place sort via partitioning — the common default, with O(n²) worst case.

def quick_sort(arr: list, low: int = 0, high: int = None) -> list:
    if high is None:
        high = len(arr) - 1
    if low < high:
        pivot_idx = partition(arr, low, high)
        quick_sort(arr, low, pivot_idx - 1)
        quick_sort(arr, pivot_idx + 1, high)
    return arr

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

Complexity comparison¶

How the common sorts and searches trade off time, space, and stability.

Algorithm	Best	Average	Worst	Space	Stable
Bubble sort	O(n)	O(n²)	O(n²)	O(1)	Yes
Insertion sort	O(n)	O(n²)	O(n²)	O(1)	Yes
Merge sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes
Quick sort	O(n log n)	O(n log n)	O(n²)	O(log n)	No
Heap sort	O(n log n)	O(n log n)	O(n log n)	O(1)	No
TimSort (Python)	O(n)	O(n log n)	O(n log n)	O(n)	Yes

Practice Exercises¶

Implement binary search for finding the leftmost occurrence of a value.
Implement merge sort and count inversions (pairs where arr[i] > arr[j] and i < j).
Implement quick sort with random pivot selection (avoid worst case).
Use bisect module for efficient sorted-list operations.
Benchmark all sorts on 100K random integers — verify theoretical complexities.

💬 Discussion

Have a question about this topic? Found an error? Share your thoughts below.