In-place merge sort in Python
Merge sort using O(1) extra space via in-place merging, at a cost in running time.
- File
in_place_merge_sort.py, 89 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/in-place-merge-sort/. The authors are listed in prov/JZA43S.jsonl.
from typing import Protocol, TypeVar
class Ordered(Protocol):
def __lt__(self, other: "Ordered", /) -> bool: ...
T = TypeVar("T", bound=Ordered)
def _reverse(a: list[T], i: int, j: int) -> None:
j -= 1
while i < j:
a[i], a[j] = a[j], a[i]
i += 1
j -= 1
def rotate(a: list[T], i: int, m: int, j: int) -> None:
"""Turn a[i:m] + a[m:j] into a[m:j] + a[i:m] with three reversals."""
if i == m or m == j: # @line L16
return
_reverse(a, i, m)
_reverse(a, m, j)
_reverse(a, i, j)
def _lower_bound(a: list[T], lo: int, hi: int, x: T) -> int:
while lo < hi: # @line L17
m = (lo + hi) // 2
if a[m] < x:
lo = m + 1
else:
hi = m
return lo # @line L18
def _upper_bound(a: list[T], lo: int, hi: int, x: T) -> int:
while lo < hi: # @line L19
m = (lo + hi) // 2
if x < a[m]:
hi = m
else:
lo = m + 1
return lo # @line L20
def merge_in_place(a: list[T], lo: int, mid: int, hi: int) -> None:
"""Stably merge the sorted runs a[lo:mid] and a[mid:hi] with no buffer."""
if lo == mid or mid == hi: # @line L6
return
if hi - lo == 2: # @line L7
if a[mid] < a[lo]:
a[lo], a[mid] = a[mid], a[lo]
return
if mid - lo >= hi - mid: # @line L8
cut1 = lo + (mid - lo) // 2 # @line L9
cut2 = _lower_bound(a, mid, hi, a[cut1])
else: # @line L10
cut2 = mid + (hi - mid) // 2 # @line L11
cut1 = _upper_bound(a, lo, mid, a[cut2])
rotate(a, cut1, mid, cut2) # @line L12
new_mid = cut1 + (cut2 - mid) # @line L13
merge_in_place(a, lo, cut1, new_mid) # @line L14
merge_in_place(a, new_mid, cut2, hi) # @line L15
def _sort(a: list[T], lo: int, hi: int) -> None:
if hi - lo < 2: # @line L1
return
mid = (lo + hi) // 2 # @line L2
_sort(a, lo, mid) # @line L3
_sort(a, mid, hi) # @line L4
merge_in_place(a, lo, mid, hi) # @line L5
def in_place_merge_sort(a: list[T]) -> None:
"""Sort a in place, stably, in non-decreasing order.
Top-down merge sort whose merge uses no buffer: it splits the longer run
at its middle item, finds the matching cut in the other run by binary
search, swaps the two middle blocks with a rotation, and merges the two
smaller pairs of runs that result.
Cost: O(n log n) comparisons, O(n log² n) moves and time, O(log n) stack.
"""
_sort(a, 0, len(a))
test_in_place_merge_sort.py 83 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/in-place-merge-sort/. The authors are listed in prov/JZA43S.jsonl.
import itertools
import random
from in_place_merge_sort import in_place_merge_sort, merge_in_place, rotate
class Key:
def __init__(self, k: int, tag: int) -> None:
self.k, self.tag = k, tag
def __lt__(self, other: "Key") -> bool:
return self.k < other.k
def test_example() -> None:
a = [1, 4, 6, 8, 2, 3, 5, 7]
merge_in_place(a, 0, 4, 8)
assert a == [1, 2, 3, 4, 5, 6, 7, 8]
b = [5, 1, 4, 2, 8, 0, 3, 6]
in_place_merge_sort(b)
assert b == [0, 1, 2, 3, 4, 5, 6, 8]
def test_rotate() -> None:
a = [6, 8, 2, 3, 5]
rotate(a, 0, 2, 5)
assert a == [2, 3, 5, 6, 8]
b = [1, 2, 3]
rotate(b, 0, 0, 3)
rotate(b, 0, 3, 3)
assert b == [1, 2, 3]
def test_edges() -> None:
for a in ([], [1], [2, 1], [1, 2], [1, 1, 1], [3, 2, 1], [2**63 - 1, -(2**63)], [2**63 - 1, 0, -(2**63), 2**63 - 1]):
b = list(a)
in_place_merge_sort(b)
assert b == sorted(a)
def test_all_permutations() -> None:
for n in range(8):
for p in itertools.permutations(range(n)):
b = list(p)
in_place_merge_sort(b)
assert b == list(range(n))
def test_merge_of_all_run_lengths() -> None:
rng = random.Random(5)
for l1 in range(12):
for l2 in range(12):
x = sorted(rng.randint(0, 5) for _ in range(l1))
y = sorted(rng.randint(0, 5) for _ in range(l2))
a = [Key(v, i) for i, v in enumerate(x + y)]
merge_in_place(a, 0, l1, l1 + l2)
assert [(e.k, e.tag) for e in a] == sorted((e.k, e.tag) for e in a)
def test_stable() -> None:
rng = random.Random(2004)
for _ in range(200):
a = [Key(rng.randint(0, 4), i) for i in range(rng.randint(0, 60))]
in_place_merge_sort(a)
assert [(e.k, e.tag) for e in a] == sorted((e.k, e.tag) for e in a)
def test_random_against_sorted() -> None:
rng = random.Random(1981)
for _ in range(600):
a = [rng.randint(-30, 30) for _ in range(rng.randint(0, 80))]
b = list(a)
in_place_merge_sort(b)
assert b == sorted(a)
def test_strings() -> None:
a = ["pear", "fig", "apple", "fig", "kiwi"]
in_place_merge_sort(a)
assert a == ["apple", "fig", "fig", "kiwi", "pear"]
What the next level needs
- the tests did not run in this build