Natural merge sort in Python
Merge sort that first detects existing ascending runs and merges them; adaptive to presorted input.
- File
natural_merge_sort.py, 54 lines- Level
- I0 not checked yet
- 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/natural-merge-sort/. The authors are listed in prov/8CJ9C7.jsonl.
from typing import Protocol, TypeVar
class Ordered(Protocol):
def __lt__(self, other: "Ordered", /) -> bool: ...
T = TypeVar("T", bound=Ordered)
def run_bounds(a: list[T]) -> list[int]:
"""Return [0, b_1, ..., b_r] with b_r = len(a): a[b_{t-1}:b_t] are the maximal non-decreasing runs."""
n = len(a)
bounds = [0]
for i in range(1, n):
if a[i] < a[i - 1]: # a run ends before index i
bounds.append(i)
if n > 0:
bounds.append(n)
return bounds
def natural_merge_sort(a: list[T]) -> None:
"""Sort a in place, stably, by merging its natural runs pass by pass."""
b = run_bounds(a) # @line L1
while len(b) > 2: # @line L2
c = [0] # @line L3
for t in range(2, len(b), 2): # @line L4
merge(a, b[t - 2], b[t - 1], b[t]) # @line L5
c.append(b[t]) # @line L6
if len(b) % 2 == 0: # @line L7
c.append(b[-1])
b = c # @line L8
def merge(a: list[T], lo: int, mid: int, hi: int) -> None:
"""Merge the sorted parts a[lo:mid] and a[mid:hi] into a[lo:hi]; on a tie, the left item goes first."""
left = a[lo:mid]
i, j, k = 0, mid, lo
while i < len(left) and j < hi:
if a[j] < left[i]:
a[k] = a[j]
j += 1
else:
a[k] = left[i]
i += 1
k += 1
while i < len(left):
a[k] = left[i]
i += 1
k += 1
test_natural_merge_sort.py 75 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/natural-merge-sort/. The authors are listed in prov/8CJ9C7.jsonl.
import itertools
import random
from natural_merge_sort import natural_merge_sort, run_bounds
class Counted:
count = 0
def __init__(self, key: int, tag: int = 0) -> None:
self.key = key
self.tag = tag
def __lt__(self, other: "Counted") -> bool:
Counted.count += 1
return self.key < other.key
def test_example() -> None:
a = [3, 8, 9, 2, 5, 1, 4, 6, 7, 0]
assert run_bounds(a) == [0, 3, 5, 9, 10]
natural_merge_sort(a)
assert a == list(range(10))
def test_example_count() -> None:
a = [Counted(x) for x in [3, 8, 9, 2, 5, 1, 4, 6, 7, 0]]
Counted.count = 0
natural_merge_sort(a)
assert Counted.count == 9 + 3 + 1 + 8
def test_sorted_is_linear() -> None:
n = 1000
a = [Counted(i) for i in range(n)]
Counted.count = 0
natural_merge_sort(a)
assert Counted.count == n - 1
def test_edges() -> None:
for a in ([], [1], [2, 1], [1, 1], [3, 2, 1], [1, 3, 2]):
b = list(a)
natural_merge_sort(b)
assert b == sorted(a)
assert run_bounds([]) == [0]
def test_all_permutations() -> None:
for n in range(8):
for p in itertools.permutations(range(n)):
a = list(p)
natural_merge_sort(a)
assert a == list(range(n))
def test_stable() -> None:
rng = random.Random(2)
for _ in range(200):
keys = [rng.randint(0, 4) for _ in range(rng.randint(0, 40))]
a = [Counted(k, t) for t, k in enumerate(keys)]
natural_merge_sort(a)
assert [(x.key, x.tag) for x in a] == sorted((x.key, x.tag) for x in a)
def test_random() -> None:
rng = random.Random(8)
for _ in range(100):
a = [rng.randint(-50, 50) for _ in range(rng.randint(0, 300))]
b = list(a)
natural_merge_sort(b)
assert b == sorted(a)
What the next level needs
- the tests did not run in this build