A generic typesafe stack-based iterative in-place implementation of the Median-of-Three Quicksort algorithm in Python.

quicksort.py

from random import sample
from typing import Callable, Protocol, TypeVar


class Comparable(Protocol):
    """
    Summary
    -------
    a protocol for comparable types
    """
    __lt__: Callable[..., bool]
    __gt__: Callable[..., bool]
    __le__: Callable[..., bool]
    __ge__: Callable[..., bool]
    __eq__: Callable[..., bool]
    __ne__: Callable[..., bool]


T = TypeVar('T', bound=Comparable)


def quicksort(
    array: list[T],
    predicate: Callable[[T, T], bool] = lambda current, next: current < next,
) -> list[T]:
    """
    Summary
    -------
    sorts an array using a stack-based iterative median-of-three quicksort algorithm

    Parameters
    ----------
    array (List[T]) : the array to be sorted
    predicate (Callable[[T, T], bool]): the predicate to be used for sorting

    Returns
    -------
    array (List[T]) : the sorted array
    """
    stack: list[tuple[int, int]] = [(0, len(array) - 1)]

    while stack:
        lo, hi = stack.pop()
        i = lo - 1
        pivot1, pivot2, pivot3 = sample(range(lo, hi + 1), 3)

        if array[pivot2] < array[pivot1]:
            pivot1, pivot2 =\
            pivot2, pivot1

        if array[pivot3] < array[pivot2]:
            pivot2, pivot3 =\
            pivot3, pivot2

            if array[pivot2] < array[pivot1]:
                pivot1, pivot2 =\
                pivot2, pivot1

        for j in range(lo, hi):
            if not predicate(array[j], array[pivot2]):
                i += 1
                array[i], array[j] =\
                array[j], array[i]

        array[i + 1], array[hi] =\
        array[hi]   , array[i + 1]

        if i > lo:
            stack.append((lo, i))

        if (index := i + 2) < hi:
            stack.append((index, hi))

    return array