sorts.smoothsort
================

.. py:module:: sorts.smoothsort

.. autoapi-nested-parse::

   Smoothsort algorithm implementation.

   Smoothsort is an adaptive, in-place comparison sort invented by Edsger W. Dijkstra.
   It runs in O(n log n) worst-case and degrades gracefully to O(n) for nearly sorted data.
   It uses a forest of Leonardo heaps to achieve this adaptive behaviour.

   Reference:
       https://en.wikipedia.org/wiki/Smoothsort
       https://www.cs.utexas.edu/~EWD/ewd07xx/EWD796a.PDF



Attributes
----------

.. autoapisummary::

   sorts.smoothsort._LEONARDO
   sorts.smoothsort.results


Functions
---------

.. autoapisummary::

   sorts.smoothsort._sift
   sorts.smoothsort._trinkle
   sorts.smoothsort.smoothsort


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

.. py:function:: _sift(seq: list[int], root: int, order: int) -> None

   Restore the max-heap property within a Leonardo tree of the given ``order``.

   Sifts ``seq[root]`` downward until the subtree satisfies the Leonardo
   max-heap invariant: every node is >= both of its children.
   Trees of order 0 or 1 are single nodes and already satisfy the invariant.

   In a Leonardo tree of order k rooted at index ``root``:
     - the right child root is at ``root - 1``
     - the left  child root is at ``root - 1 - L(k-2)``

   Args:
       seq:   The list being sorted (mutated in-place).
       root:  Index of the root of the Leonardo tree to fix.
       order: Leonardo order of the tree rooted at ``root``.

   Examples:
       >>> data = [3, 5, 4]
       >>> _sift(data, 2, 2)
       >>> data
       [3, 4, 5]

       >>> data = [1, 2, 3]
       >>> _sift(data, 2, 2)
       >>> data
       [1, 2, 3]

       >>> data = [7]
       >>> _sift(data, 0, 1)
       >>> data
       [7]

       >>> data = [9, 1, 8, 5, 3]
       >>> _sift(data, 4, 3)
       >>> data
       [3, 1, 9, 5, 8]


.. py:function:: _trinkle(seq: list[int], pos: int, heap_sizes: list[int], idx: int) -> None

   Restore both the inter-heap root ordering and the intra-heap ordering.

   Walks the value at ``pos`` leftwards through the forest-root chain as
   long as the left-neighbour root is larger, then calls ``_sift`` to fix
   the heap at the final resting position.

   Args:
       seq:        The list being sorted (mutated in-place).
       pos:        Index of the root being inserted or newly exposed.
       heap_sizes: List of Leonardo orders for the current forest (left to
                   right); ``heap_sizes[idx]`` is the order of the tree
                   whose root is at ``pos``.
       idx:        Position in ``heap_sizes`` for the tree rooted at ``pos``.

   Examples:
       >>> data = [1, 5, 3]
       >>> _trinkle(data, 2, [1, 1], 1)
       >>> data
       [1, 3, 5]

       >>> data = [3, 5, 4]
       >>> _trinkle(data, 2, [2], 0)
       >>> data
       [3, 4, 5]


.. py:function:: smoothsort(seq: list[int]) -> list[int]

   Sort a list in-place using the Smoothsort algorithm and return it.

   Smoothsort (Edsger W. Dijkstra, 1981) is an adaptive, in-place sort
   with O(n log n) worst-case time and O(n) best-case time on already-sorted
   input.  It improves on Heapsort by maintaining a forest of Leonardo heaps
   whose structure mirrors the sorted prefix of the sequence.

   Args:
       seq: A list of integers to sort.

   Returns:
       The same list object, sorted in ascending order.

   Examples:
       >>> smoothsort([4, 1, 3, 9, 7])
       [1, 3, 4, 7, 9]
       >>> smoothsort([])
       []
       >>> smoothsort([1])
       [1]
       >>> smoothsort([5, 4, 3, 2, 1])
       [1, 2, 3, 4, 5]
       >>> smoothsort([3, 3, 2, 1, 2])
       [1, 2, 2, 3, 3]
       >>> smoothsort([1, 2, 3, 4, 5])
       [1, 2, 3, 4, 5]
       >>> smoothsort([-3, 0, -1, 5, 2])
       [-3, -1, 0, 2, 5]


.. py:data:: _LEONARDO
   :type:  list[int]
   :value: [1, 1]


.. py:data:: results