Linked-list merge sort in Python
Mergesort on a linked list that splits and merges nodes by relinking them, needing no auxiliary array.
- File
linked_list_merge_sort.py, 70 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/linked-list-merge-sort/. The authors are listed in prov/NEN2CA.jsonl.
from typing import Generic, Optional, Protocol, TypeVar
class Ordered(Protocol):
def __lt__(self, other: "Ordered", /) -> bool: ...
T = TypeVar("T", bound=Ordered)
class Node(Generic[T]):
"""A node of a singly linked list."""
__slots__ = ("key", "next")
def __init__(self, key: T, next: "Optional[Node[T]]" = None) -> None:
self.key = key
self.next = next
def sort_list(head: Optional[Node[T]]) -> tuple[Optional[Node[T]], int]:
"""Sort a singly linked list by relinking its nodes; return the new head and the comparisons.
Bottom-up merge sort: pass k merges neighbouring sorted runs of w = 2^k
nodes. It uses O(1) extra space and is stable.
Cost: at most n * ceil(lg n) comparisons and ceil(lg n) passes.
"""
if head is None:
return None, 0
comparisons = 0
dummy: Node[T] = Node(head.key)
w = 1 # @line L1
while True: # @line L2
tail, p, merges = dummy, head, 0 # @line L3
while p is not None: # @line L4
merges += 1 # @line L5
q, a = p, 0 # @line L6: q goes w nodes past p, a counts them
while a < w and q is not None:
q, a = q.next, a + 1
b = w # @line L7
while a > 0 or (b > 0 and q is not None): # @line L8
if a > 0 and b > 0 and q is not None:
comparisons += 1
if a == 0 or (b > 0 and q is not None and q.key < p.key): # @line L9
e, q, b = q, q.next, b - 1
else: # @line L10
e, p, a = p, p.next, a - 1
tail.next = e # @line L11
tail = e
p = q # @line L12
tail.next = None # @line L13
if merges <= 1: # @line L14
return dummy.next, comparisons
head, w = dummy.next, 2 * w # @line L15
def linked_list_merge_sort(a: list[T]) -> int:
"""Sort the list a in place with the linked-list merge sort; return the comparisons."""
head: Optional[Node[T]] = None
for x in reversed(a):
head = Node(x, head)
head, comparisons = sort_list(head)
i = 0
while head is not None:
a[i] = head.key
head, i = head.next, i + 1
return comparisons
test_linked_list_merge_sort.py 60 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/linked-list-merge-sort/. The authors are listed in prov/NEN2CA.jsonl.
import itertools
import random
from linked_list_merge_sort import Node, linked_list_merge_sort, sort_list
def test_example() -> None:
a = [5, 1, 4, 2, 8, 0, 3]
assert linked_list_merge_sort(a) == 14
assert a == [0, 1, 2, 3, 4, 5, 8]
def test_nodes_are_relinked_not_copied() -> None:
nodes = [Node(k) for k in (3, 1, 2)]
nodes[0].next, nodes[1].next = nodes[1], nodes[2]
head, _ = sort_list(nodes[0])
assert head is nodes[1] and head.next is nodes[2] and head.next.next is nodes[0]
assert nodes[0].next is None
def test_edges() -> None:
for a in ([], [1], [2, 1], [1, 2], [1, 1, 1], [3, 2, 1], [2**63 - 1, -(2**63)]):
b = list(a)
linked_list_merge_sort(b)
assert b == sorted(a)
def test_all_permutations_and_comparison_bound() -> None:
for n in range(1, 8):
for p in itertools.permutations(range(n)):
b = list(p)
c = linked_list_merge_sort(b)
assert b == list(range(n))
assert c <= n * (n - 1).bit_length()
def test_stable() -> None:
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
rng = random.Random(11)
a = [Key(rng.randint(0, 5), i) for i in range(200)]
linked_list_merge_sort(a)
assert all((a[i].k, a[i].tag) < (a[i + 1].k, a[i + 1].tag) for i in range(199))
def test_random_against_sorted() -> None:
rng = random.Random(1945)
for _ in range(600):
a = [rng.randint(-30, 30) for _ in range(rng.randint(0, 80))]
b = list(a)
linked_list_merge_sort(b)
assert b == sorted(a)
What the next level needs
- the tests did not run in this build