Radix exchange sort in Python
MSD radix sort on bits, partitioning each recursion level by the current bit of the keys.
- File
radix_exchange_sort.py, 35 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/radix-exchange-sort/. The authors are listed in prov/Y3DQBZ.jsonl.
def radix_exchange_sort(a: list[int], w: int | None = None) -> list[int]:
"""Sort the list a of non-negative integers in place, and return it.
Precondition: 0 <= x < 2**w for each x; by default w is the bit length
of the largest key. The sort is not stable. The cost is O(n w) time in
the worst case and O(w) extra space for the stack.
"""
if any(x < 0 for x in a):
raise ValueError("the keys must be non-negative")
if w is None:
w = max(a, default=0).bit_length()
elif any(x >> w for x in a):
raise ValueError("a key has more than w bits")
stack = [(0, len(a), w - 1)] # @line L1
while stack: # @line L2
lo, hi, b = stack.pop() # @line L3
if hi - lo <= 1 or b < 0: # @line L4
continue
i, j = lo, hi - 1 # @line L5
while i <= j: # @line L6
while i <= j and not (a[i] >> b) & 1: # @line L7
i += 1
while i <= j and (a[j] >> b) & 1: # @line L8
j -= 1
if i < j: # @line L9
a[i], a[j] = a[j], a[i]
i += 1
j -= 1
stack.append((i, hi, b - 1)) # @line L10
stack.append((lo, i, b - 1))
return a # @line L11
test_radix_exchange_sort.py 41 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/radix-exchange-sort/. The authors are listed in prov/Y3DQBZ.jsonl.
import random
import unittest
from radix_exchange_sort import radix_exchange_sort
class TestRadixExchangeSort(unittest.TestCase):
def test_page_example(self):
a = [5, 2, 7, 1, 4, 6, 0, 3]
self.assertEqual(radix_exchange_sort(a, w=3), [0, 1, 2, 3, 4, 5, 6, 7])
def test_in_place(self):
a = [3, 1, 2]
self.assertIs(radix_exchange_sort(a), a)
self.assertEqual(a, [1, 2, 3])
def test_edges(self):
self.assertEqual(radix_exchange_sort([]), [])
self.assertEqual(radix_exchange_sort([0]), [0])
self.assertEqual(radix_exchange_sort([0, 0, 0]), [0, 0, 0])
self.assertEqual(radix_exchange_sort([9] * 7), [9] * 7)
self.assertEqual(radix_exchange_sort([2**64 - 1, 0, 2**63]), [0, 2**63, 2**64 - 1])
self.assertEqual(radix_exchange_sort(list(range(50, 0, -1))), list(range(1, 51)))
with self.assertRaises(ValueError):
radix_exchange_sort([-1, 2])
with self.assertRaises(ValueError):
radix_exchange_sort([8], w=3)
def test_random(self):
rng = random.Random(1959)
for _ in range(700):
n = rng.randint(0, 60)
hi = rng.choice([1, 2, 16, 1000, 2**32, 2**64])
a = [rng.randrange(hi) for _ in range(n)]
self.assertEqual(radix_exchange_sort(list(a)), sorted(a))
if __name__ == "__main__":
unittest.main()
What the next level needs
- the tests did not run in this build