Insertion sort in Python
Sort an array one item at a time. Take the next item and move it left until the item before it is not larger.
- File
insertion_sort.py, 22 lines- Level
- Native tests
- pass in this build
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/insertion-sort/. The authors are listed in prov/3NS7RT.jsonl.
from typing import Protocol, TypeVar
class Ordered(Protocol):
def __lt__(self, other: "Ordered", /) -> bool: ...
T = TypeVar("T", bound=Ordered)
def insertion_sort(a: list[T]) -> None:
"""Sort the list a in place, in non-decreasing order. The sort is stable."""
for i in range(1, len(a)): # @line L1
key = a[i] # @line L2
j = i - 1 # @line L3
while j >= 0 and key < a[j]: # @line L4
a[j + 1] = a[j] # @line L5
j -= 1 # @line L6
a[j + 1] = key # @line L7
test_insertion_sort.py 43 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/insertion-sort/. The authors are listed in prov/3NS7RT.jsonl.
import random
from insertion_sort import insertion_sort
def test_example() -> None:
a = [5, 2, 4, 6, 1, 3]
insertion_sort(a)
assert a == [1, 2, 3, 4, 5, 6]
def test_edges() -> None:
for a in ([], [1], [2, 1], [1, 1, 1], [3, 2, 1]):
b = list(a)
insertion_sort(b)
assert b == sorted(a)
def test_stable() -> None:
a = [(2, "a"), (1, "b"), (2, "c"), (1, "d")]
class Key:
def __init__(self, p: tuple[int, str]) -> None:
self.p = p
def __lt__(self, other: "Key") -> bool:
return self.p[0] < other.p[0]
b = [Key(p) for p in a]
insertion_sort(b)
assert [k.p for k in b] == [(1, "b"), (1, "d"), (2, "a"), (2, "c")]
def test_random_against_sorted() -> None:
rng = random.Random(2150)
for _ in range(500):
a = [rng.randint(-50, 50) for _ in range(rng.randint(0, 40))]
b = list(a)
insertion_sort(b)
assert b == sorted(a)
What the next level needs
- I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work