The Cycle sort algorithm simple and readable implementation in Python

cycle_sort.py

from typing import List


def cycle_sort(lst: List[int]) -> None:
    """The Cycle sort algorithm.

    The sorted list is placed in place.
    Wikipedia: https://en.wikipedia.org/wiki/Cycle_sort
    """
    for i in range(len(lst) - 1):
        item = lst[i]
        smaller_count = i + count_smaller(lst, item, start=i + 1)

        # The cycle ends when no "forward" swap is needed
        while smaller_count > i:
            while lst[smaller_count] == item:
                smaller_count += 1

            lst[i], lst[smaller_count] = lst[smaller_count], lst[i]

            item = lst[i]
            smaller_count = i + count_smaller(lst, item, start=i + 1)


def count_smaller(lst: List[int], num: int, start: int = 0) -> int:
    """Returns the number of items in the list smaller than `num`.

    The count is from the `start` index.

    Usage of sum is clever in this case but less efficient:
    (also look at: https://stackoverflow.com/q/62975325/11808461)
    >> return sum((lst[i] < num for i in range(start, len(lst))))    
    """
    count = 0
    for i in range(start, len(lst)):
        if lst[i] < num:
            count += 1
    return count