Sorting Algorithms¶

def quicksort(arr: list[int], lo: int = 0, hi: int | None = None) -> None:
    """In-place. Partitions around arr[hi] (last element as pivot)."""
    if hi is None:
        hi = len(arr) - 1
    if lo >= hi:
        return

    pivot = arr[hi]
    i = lo
    for j in range(lo, hi):
        if arr[j] < pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[hi] = arr[hi], arr[i]  # pivot lands at its final sorted position

    quicksort(arr, lo, i - 1)
    quicksort(arr, i + 1, hi)
    # Time: O(n log n) average, O(n²) worst case (already-sorted input + last-element pivot)
    # Space: O(log n) recursion stack average, O(n) worst case
    # Not stable — the partition swap can reorder equal elements

def merge_sort(arr: list[int]) -> list[int]:
    """Returns a new sorted list. Not in-place — needs O(n) auxiliary space."""
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return _merge(left, right)
    # Time: O(n log n) always — no worst-case degradation
    # Space: O(n) for the merge buffers


def _merge(left: list[int], right: list[int]) -> list[int]:
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:      # <= (not <) preserves stability: ties keep left's order
            merged.append(left[i]); i += 1
        else:
            merged.append(right[j]); j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged

def heapsort(arr: list[int]) -> None:
    """In-place. Build a max-heap, then repeatedly move the max to the end."""
    n = len(arr)

    for i in range(n // 2 - 1, -1, -1):  # bottom-up heapify, O(n)
        _sift_down(arr, i, n)

    for end in range(n - 1, 0, -1):
        arr[0], arr[end] = arr[end], arr[0]  # max is always at root
        _sift_down(arr, 0, end)              # restore heap property in the shrunk heap
    # Time: O(n log n) always — heapify O(n) + n sift-downs of O(log n)
    # Space: O(1) extra — sorts in place


def _sift_down(arr: list[int], i: int, n: int) -> None:
    while True:
        left, right, largest = 2 * i + 1, 2 * i + 2, i
        if left < n and arr[left] > arr[largest]:
            largest = left
        if right < n and arr[right] > arr[largest]:
            largest = right
        if largest == i:
            break
        arr[i], arr[largest] = arr[largest], arr[i]
        i = largest

def bucket_sort(arr: list[float], bucket_count: int = 10) -> list[float]:
    """Assumes values are roughly uniformly distributed over [0, 1).
    For integers, adapt the bucket-index formula to your value range."""
    if not arr:
        return arr

    buckets: list[list[float]] = [[] for _ in range(bucket_count)]
    for v in arr:
        idx = min(bucket_count - 1, int(v * bucket_count))  # O(1) bucket assignment
        buckets[idx].append(v)

    for b in buckets:
        b.sort()  # insertion sort in practice — buckets are small

    result = []
    for b in buckets:
        result.extend(b)
    return result
    # Time: O(n + k) average, when input is uniformly distributed across k buckets
    #        (each bucket gets ~n/k elements, so sorting all buckets is
    #        k * O((n/k)²) = O(n²/k) — with k ≈ n, that's O(n))
    # Time: O(n²) worst case — all elements land in one bucket (skewed input)
    # Space: O(n + k) for the buckets
    # Stable if the per-bucket sort is stable (e.g. insertion sort)

import heapq

def k_way_merge(sorted_chunk_iterators: list) -> list:
    """Merge k already-sorted, disk-backed iterators using O(k) memory.
    Each iterator yields its chunk's elements in ascending order."""
    heap = []  # (value, chunk_index) — heapq compares tuples, ties break on chunk_index
    iterators = [iter(chunk) for chunk in sorted_chunk_iterators]

    for i, it in enumerate(iterators):
        first = next(it, None)
        if first is not None:
            heapq.heappush(heap, (first, i))

    result = []
    while heap:
        value, i = heapq.heappop(heap)
        result.append(value)
        nxt = next(iterators[i], None)
        if nxt is not None:
            heapq.heappush(heap, (nxt, i))

    return result
    # Time: O(n log k) — n total elements, each push/pop is O(log k)
    # Space: O(k) in memory — only one element per run resident at a time,
    #        plus whatever output buffering you choose

def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
    """Sorting by start makes overlap checking a single linear pass."""
    intervals.sort(key=lambda iv: iv[0])
    merged = [intervals[0]]

    for start, end in intervals[1:]:
        if start <= merged[-1][1]:          # overlaps the last merged interval
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])

    return merged
    # Time: O(n log n) for the sort, O(n) for the sweep

import random

def find_kth_largest(nums: list[int], k: int) -> int:
    """Quickselect: only recurse into the side containing the answer. O(n) average."""
    target = len(nums) - k  # k-th largest = index (n-k) in ascending sorted order

    def partition(lo: int, hi: int) -> int:
        pivot_idx = random.randint(lo, hi)
        nums[pivot_idx], nums[hi] = nums[hi], nums[pivot_idx]
        pivot = nums[hi]
        i = lo
        for j in range(lo, hi):
            if nums[j] < pivot:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
        nums[i], nums[hi] = nums[hi], nums[i]
        return i

    lo, hi = 0, len(nums) - 1
    while True:
        p = partition(lo, hi)
        if p == target:
            return nums[p]
        elif p < target:
            lo = p + 1
        else:
            hi = p - 1
    # Time: O(n) average (halves the search space like binary search), O(n²) worst case

def sort_colors(nums: list[int]) -> None:
    """In-place sort of 0s, 1s, 2s in one pass — the partition step of 3-way quicksort."""
    low, mid, high = 0, 0, len(nums) - 1

    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1; mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1  # don't advance mid — the swapped-in value is unexamined
    # Time: O(n), single pass  Space: O(1)