sorts.power_sort
================

.. py:module:: sorts.power_sort

.. autoapi-nested-parse::

   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
----------

.. autoapisummary::

   sorts.power_sort.user_input


Functions
---------

.. autoapisummary::

   sorts.power_sort._find_run
   sorts.power_sort._merge
   sorts.power_sort._node_power
   sorts.power_sort.power_sort


Module Contents
---------------

.. py:function:: _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]


.. py:function:: _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]


.. py:function:: _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


.. py:function:: 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


.. py:data:: user_input