Quickselect in Python

from bisect import bisect_left

# Quickselect in Python
#
# PURPOSE
# Quickselect finds a zero-based order statistic without fully sorting the input.
#
# METHOD
# Partition around the middle-position pivot using a three-way partition. Retain only the
# side containing rank k, or return the pivot when k lies in the equal region.
#
# COMPLEXITY
# O(n) expected time for random input; O(n squared) worst case for this deterministic pivot.
# O(1) auxiliary space.
#
# CONTRACT
# 0 <= k < n. Mutates input. Returns the kth smallest value, counting duplicates.
# Public APIs infer array lengths except in C, which accepts pointer/length pairs. Vertex
# counts and matrix dimensions remain explicit. Arrays must contain signed 32-bit integers.
# Sorted order, correct tree topology, and caller-owned data-structure invariants are
# preconditions; checking them on every query would change query complexity.
# Scalar and shape checks are included. Value-range checks are included where needed to
# prevent invalid indexing or nontermination. Allocation sizes are capped at 4,000,000
# workspace entries. Arithmetic outside Python raises an error on 32-bit overflow; Python
# uses arbitrary precision. Native allocation failures propagate. In-place outputs may be
# partly updated after arithmetic failure. These are single-threaded, in-memory
# implementations.
#
# LANGUAGE DETAILS
# Python 3.9+: automatic lengths, native lists, arbitrary-precision arithmetic, and
# bisect_left for LIS. Invalid scalar/shape inputs raise ValueError. Integer element types
# and sorted/tree invariants remain caller preconditions.
#
# EXAMPLE
# Expected return: 5.
# Expected a after call: [2, 2, 5, 7, 9].
# Run: python example.py
# Tests for this exact source artifact run before publication. The accompanying source
# archive includes unit cases, runtime results, and source hashes.

def alg_require(condition):
    if not condition:
        raise ValueError("invalid algorithm input; see contract")
def alg_size(n):
    alg_require(0 <= n <= 4000000)
    return n

def quickselect(a: list[int], k: int) -> int:
    alg_require(isinstance(a, list) and len(a) <= 1000000)
    alg_require(type(k) is int and -2147483648 <= k <= 2147483647)
    n: int = len(a)
    alg_require(n >= 0 and n <= 1000000)
    alg_require(len(a) == n)
    alg_require(k >= 0 and k < n)
    low: int = 0
    high: int = n - 1
    left: int = 0
    mid: int = 0
    right: int = 0
    pivot: int = 0
    temp: int = 0
    while low <= high:
        pivot = a[low + (high - low) // 2]
        left = low
        mid = low
        right = high
        while mid <= right:
            if a[mid] < pivot:
                temp = a[left]
                a[left] = a[mid]
                a[mid] = temp
                left += 1
                mid += 1
            elif a[mid] > pivot:
                temp = a[mid]
                a[mid] = a[right]
                a[right] = temp
                right -= 1
            else:
                mid += 1
        if k < left:
            high = left - 1
        elif k > right:
            low = right + 1
        else:
            return pivot
    return -1

a = [7, 2, 9, 2, 5]
k = 2
result = quickselect(a, k)
print(result)
# Expected a: [2, 2, 5, 7, 9]
print(a)