sorts.power_sort

PowerSort - An adaptive merge sort algorithm.

PowerSort is an adaptive, stable sorting algorithm that efficiently handles partially ordered data by optimally merging existing runs (consecutive sequences of sorted elements) in the input. It was developed by J. Ian Munro and Sebastian Wild and has been integrated into Python’s standard library since version 3.11.

The algorithm works by: 1. Detecting naturally occurring runs (ascending or descending sequences) 2. Using a power-based merge strategy to determine optimal merge order 3. Maintaining a stack of runs and merging based on calculated node powers

Time Complexity: O(n log n) worst case, O(n) for nearly sorted data Space Complexity: O(n) for merge buffer

References: - https://en.wikipedia.org/wiki/Powersort - https://arxiv.org/abs/1805.04154 (Original paper by Munro and Wild)

For doctests run: python -m doctest -v power_sort.py

For manual testing run: python power_sort.py

Attributes

user_input

Functions

_find_run(→ int)	Detect a run (ascending or descending sequence) starting at 'start'.
_merge(→ None)	Merge two adjacent sorted runs in-place using auxiliary space.
_node_power(→ int)	Calculate the node power for two adjacent runs.
power_sort(→ list)	Sort a list using the PowerSort algorithm.

Module Contents

sorts.power_sort._find_run(arr: list, start: int, end: int, key: collections.abc.Callable[[Any], Any] | None = None) → int

Detect a run (ascending or descending sequence) starting at ‘start’.

If the run is descending, reverse it in-place to make it ascending. Returns the end index (exclusive) of the detected run.

Args:

arr: The list to search in start: Starting index of the run end: End index (exclusive) of the search range key: Optional key function for comparisons

Returns:

End index (exclusive) of the detected run

>>> arr = [3, 2, 1, 4, 5, 6]
>>> _find_run(arr, 0, 6)
3
>>> arr
[1, 2, 3, 4, 5, 6]
>>> arr = [1, 2, 3, 2, 1]
>>> _find_run(arr, 0, 5)
3
>>> arr
[1, 2, 3, 2, 1]

sorts.power_sort._merge(arr: list, start1: int, end1: int, end2: int, key: collections.abc.Callable[[Any], Any] | None = None) → None

Merge two adjacent sorted runs in-place using auxiliary space.

Merges arr[start1:end1] with arr[end1:end2].

Args:

arr: The list containing the runs start1: Start index of first run end1: End index of first run (start of second run) end2: End index of second run key: Optional key function for comparisons

>>> arr = [1, 3, 5, 2, 4, 6]
>>> _merge(arr, 0, 3, 6)
>>> arr
[1, 2, 3, 4, 5, 6]
>>> arr = [5, 6, 7, 1, 2, 3]
>>> _merge(arr, 0, 3, 6)
>>> arr
[1, 2, 3, 5, 6, 7]

sorts.power_sort._node_power(total_length: int, b1: int, n1: int, b2: int, n2: int) → int

Calculate the node power for two adjacent runs.

This determines the merge priority in the stack. The power is the smallest integer p such that floor(a * 2^p) != floor(b * 2^p), where: - a = (b1 + n1/2) / n - b = (b2 + n2/2) / n

Args:

total_length: Total length of the array b1: Start index of first run n1: Length of first run b2: Start index of second run n2: Length of second run

Returns:

The calculated node power

>>> _node_power(100, 0, 25, 25, 25)
2
>>> _node_power(100, 0, 50, 50, 50)
1

sorts.power_sort.power_sort(collection: list, *, key: collections.abc.Callable[[Any], Any] | None = None, reverse: bool = False) → list

Sort a list using the PowerSort algorithm.

PowerSort is an adaptive merge sort that detects existing runs in the data and uses a power-based merging strategy for optimal performance.

Args:

collection: A mutable ordered collection with comparable items key: Optional function to extract comparison key from each element reverse: If True, sort in descending order

Returns:

The same collection ordered according to the parameters

Time Complexity: O(n log n) worst case, O(n) for nearly sorted data Space Complexity: O(n)

Examples: >>> power_sort([0, 5, 3, 2, 2]) [0, 2, 2, 3, 5] >>> power_sort([]) [] >>> power_sort([1]) [1] >>> power_sort([-2, -5, -45]) [-45, -5, -2] >>> power_sort([1, 2, 3, 4, 5]) [1, 2, 3, 4, 5] >>> power_sort([5, 4, 3, 2, 1]) [1, 2, 3, 4, 5] >>> power_sort([3, 1, 4, 1, 5, 9, 2, 6, 5]) [1, 1, 2, 3, 4, 5, 5, 6, 9] >>> power_sort([‘banana’, ‘apple’, ‘cherry’]) [‘apple’, ‘banana’, ‘cherry’] >>> power_sort([3.14, 2.71, 1.41, 1.73]) [1.41, 1.73, 2.71, 3.14] >>> power_sort([5, 2, 8, 1, 9], reverse=True) [9, 8, 5, 2, 1] >>> power_sort([‘apple’, ‘pie’, ‘a’, ‘longer’], key=len) [‘a’, ‘pie’, ‘apple’, ‘longer’] >>> power_sort([(1, ‘b’), (2, ‘a’), (1, ‘a’)], key=lambda x: x[0]) [(1, ‘b’), (1, ‘a’), (2, ‘a’)] >>> power_sort([1, 2, 3, 2, 1, 2, 3, 4]) [1, 1, 2, 2, 2, 3, 3, 4] >>> result = power_sort(list(range(100))) >>> result == list(range(100)) True >>> result = power_sort(list(reversed(range(50)))) >>> result == list(range(50)) True

sorts.power_sort.user_input