An implementation of Quicksort in Python.

from typing import List, Callable

def swap(ints: List[int], indexA: int, indexB: int) -> None:
    """Swap the values in INTS at INDEXA and INDEXB."""
    valueA = ints[indexA]
    ints[indexA] = ints[indexB]
    ints[indexB] = valueA

def partition(ints: List[int], comparator: Callable[[int, int], bool], low_index: int, high_index: int) -> int:
    """Sorts sublist into [{<= pivot}, pivot, {> than pivot}]"""
    pivot_index = high_index
    i = low_index - 1

    for j in range(low_index, high_index):
        if comparator(ints[j], ints[pivot_index]):
            i += 1
            swap(ints, i, j)
    i += 1
    swap(ints, i, pivot_index)

    return i

def quick_sort_inner(ints: List[int], comparator: Callable[[int, int], bool], low_index: int, high_index: int) -> List[int]:
    if low_index >= high_index or low_index < 0:
        return

    pivot_index = partition(ints, comparator, 0, high_index)

    quick_sort_inner(ints, comparator, 0, pivot_index - 1)
    quick_sort_inner(ints, comparator, pivot_index + 1, high_index)

    return ints

def quick_sort(ints: List[int], comparator: Callable[[int, int], bool]) -> List[int]:
       return quick_sort_inner(ints, comparator, 0, len(ints) - 1)


a = [10, 5, 8, 2, 1, 3]
print(quick_sort(a, lambda a, b: a <= b))

Links to this note