Merge sort in Python
Sort an array by divide and conquer. Sort each half, then merge the two sorted halves into one sorted array.
- File
merge_sort.py, 41 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/merge-sort/. The authors are listed in prov/4MRG7S.jsonl.
from typing import Protocol, TypeVar
class Ordered(Protocol):
def __lt__(self, other: "Ordered", /) -> bool: ...
T = TypeVar("T", bound=Ordered)
def merge_sort(a: list[T], lo: int = 0, hi: int | None = None) -> None:
"""Sort a[lo:hi] in place, in non-decreasing order. The sort is stable."""
if hi is None:
hi = len(a)
if hi - lo <= 1: # @line L1
return
mid = lo + (hi - lo) // 2 # @line L2
merge_sort(a, lo, mid) # @line L3
merge_sort(a, mid, hi) # @line L4
merge(a, lo, mid, hi) # @line L5
def merge(a: list[T], lo: int, mid: int, hi: int) -> None:
"""Merge the sorted parts a[lo:mid] and a[mid:hi] into one sorted part."""
b = a[lo:mid] # @line L6
i, j, k = 0, mid, lo # @line L7
while i < len(b) and j < hi: # @line L8
if not a[j] < b[i]: # @line L9: b[i] <= a[j], with only <
a[k] = b[i]
i += 1
else:
a[k] = a[j] # @line L10
j += 1
k += 1 # @line L11
while i < len(b): # @line L12
a[k] = b[i] # @line L13
i += 1
k += 1
test_merge_sort.py 41 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/merge-sort/. The authors are listed in prov/4MRG7S.jsonl.
import random
from merge_sort import merge_sort
def test_example() -> None:
a = [38, 27, 43, 3, 9, 82, 10]
merge_sort(a)
assert a == [3, 9, 10, 27, 38, 43, 82]
def test_edges() -> None:
for a in ([], [1], [2, 1], [1, 1, 1], [3, 2, 1], [1, 2, 3]):
b = list(a)
merge_sort(b)
assert b == sorted(a)
def test_stable() -> None:
class Key:
def __init__(self, k: int, tag: str) -> None:
self.k, self.tag = k, tag
def __lt__(self, other: "Key") -> bool:
return self.k < other.k
a = [Key(2, "a"), Key(1, "b"), Key(2, "c"), Key(1, "d"), Key(2, "e")]
merge_sort(a)
assert [x.tag for x in a] == ["b", "d", "a", "c", "e"]
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, 60))]
b = list(a)
merge_sort(b)
assert b == sorted(a)
What the next level needs
- I2 needs the differential and mutation runs (09.5, 09.6), which are M1 work