Sorting & Searching

Sorting & Searching

Sorting Complexity

| Algorithm | Best | Average | Worst | Space | Stable | Use when | |----------------|-----------|-----------|-----------|--------|--------|----------| | Merge Sort | O(n log n)| O(n log n)| O(n log n)| O(n) | Yes | Need stable sort or worst-case guarantee | | Quick Sort | O(n log n)| O(n log n)| O(n²) | O(log n)| No | General purpose, good average | | Heap Sort | O(n log n)| O(n log n)| O(n log n)| O(1) | No | In-place with guaranteed O(n log n) | | Tim Sort (Python) | O(n) | O(n log n)| O(n log n)| O(n) | Yes | Python's built-in — best for real data | | Counting Sort | O(n+k) | O(n+k) | O(n+k) | O(k) | Yes | Small integer range | | Radix Sort | O(d(n+k)) | O(d(n+k)) | O(d(n+k)) | O(n+k) | Yes | Fixed-width integers/strings |

Non-comparison sorts (Counting, Radix) break the O(n log n) lower bound — they only work on specific data types.

Python Sort

arr.sort()                      # in-place, Timsort O(n log n), stable
sorted_arr = sorted(arr)        # returns new list
arr.sort(key=lambda x: x[1])   # sort by second element
arr.sort(key=lambda x: -x)     # descending (negate for numbers)
arr.sort(reverse=True)          # descending

Merge Sort

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, 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:]

Quick Sort

def quicksort(arr, lo, hi):
    if lo < hi:
        p = partition(arr, lo, hi)
        quicksort(arr, lo, p - 1)
        quicksort(arr, p + 1, hi)

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

Binary Search

def binary_search(arr, target):
    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

# Find leftmost occurrence (lower bound)
def lower_bound(arr, target):
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] < target: left = mid + 1
        else:                 right = mid
    return left

Magic index insight: In a sorted array of distinct integers, arr[mid] < mid means the magic index must be to the right (values are too small on the left); arr[mid] > mid means search the left.

Binary Search on the Answer

# Template: "find minimum X such that condition(X) is True"
# Works when the answer space is monotonic (False, False, ..., True, True, ...)
def binary_search_answer(lo, hi, condition):
    while lo < hi:
        mid = (lo + hi) // 2
        if condition(mid): hi = mid   # might be answer, search left
        else:              lo = mid + 1
    return lo

Example uses: minimum days to complete, koko eating bananas, allocate minimum pages.

Quick Select — k-th Smallest in O(n) Average

import random

def quick_select(arr, k):
    """Find the k-th smallest element (1-indexed). Average O(n)."""
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        pivot_idx = random.randint(lo, hi)
        arr[pivot_idx], arr[hi] = arr[hi], arr[pivot_idx]
        pivot = arr[hi]
        i = lo - 1
        for j in range(lo, hi):
            if arr[j] <= pivot:
                i += 1; arr[i], arr[j] = arr[j], arr[i]
        i += 1
        arr[i], arr[hi] = arr[hi], arr[i]
        if i == k - 1:   return arr[i]
        elif i < k - 1:  lo = i + 1
        else:            hi = i - 1
    return arr[lo]

Key Interview Tips

• Python's sort() is Timsort — stable, O(n log n), and very fast on partially-sorted data
• Binary search works on any monotonic condition, not just sorted arrays
• "Find the minimum/maximum value that satisfies X" → binary search on the answer
• Use bisect module for pre-sorted arrays: bisect_left, bisect_right — no need to roll your own
• Quick sort has O(n²) worst case — use median-of-3 pivot or shuffle input to avoid it