# Powersort

# Powersort

Powersort is a stable adaptive merge sort that improves how runs are merged. It builds on the same idea as Timsort, detecting natural runs in the input, but uses a principled method to decide merge order based on a notion of power derived from positions in the array.

The goal is to achieve near optimal merge trees with low overhead.

## Problem

Given an array $A$ of length $n$, reorder it such that:

$$
A[0] \le A[1] \le \dots \le A[n-1]
$$

while preserving stability and exploiting existing runs.

## Idea

Powersort detects runs as in natural merge sort. Each run is assigned a power value that reflects its position in the array and how it should be merged.

The power approximates the depth of the run in an optimal binary merge tree.

For two adjacent runs, the power depends on their boundaries:

* earlier runs tend to have lower power
* later runs tend to have higher power

Merging is controlled by comparing powers instead of using ad hoc size rules.

## Algorithm

```text id="y6r1dv"
powersort(A):
    stack = empty

    i = 0
    while i < n:
        run = detect_run(A, i)
        power = compute_power(run)

        while stack not empty and stack.top.power >= power:
            merge top two runs on stack

        push (run, power) onto stack
        i = end of run

    while stack has more than one run:
        merge top two runs
```

The key function is power computation.

```text id="w4z2kb"
compute_power(run):
    let run cover indices [l, r]

    return number of leading equal bits
    in binary representation of midpoints
```

This approximates how runs should be merged in a balanced tree.

## Example

Let:

$$
A = [1,2,3,  7,8,  4,5,6,  9,10]
$$

Detected runs:

* [1,2,3]
* [7,8]
* [4,5,6]
* [9,10]

Each run gets a power value based on position. Merging is then guided by power ordering rather than simple size rules.

Result:

$$
[1,2,3,4,5,6,7,8,9,10]
$$

## Correctness

Each run is sorted. Merging preserves sorted order and stability. The power based merge strategy ensures that merges form a nearly optimal binary tree, which guarantees logarithmic depth. By induction over merges, the final array is sorted.

## Complexity

| case  | time          |
| ----- | ------------- |
| best  | $O(n)$        |
| worst | $O(n \log n)$ |

Space:

$$
O(n)
$$

The number of comparisons is close to the theoretical lower bound for comparison sorting.

## Properties

| property         | value        |
| ---------------- | ------------ |
| stable           | yes          |
| adaptive         | yes          |
| merge optimality | near optimal |
| in-place         | no           |

## Notes

Powersort replaces the heuristic stack rules of Timsort with a mathematically grounded strategy. It produces well balanced merge trees with minimal overhead.

It is mainly of interest in high performance library implementations where predictable behavior and optimal comparison counts matter.

## Implementation

This simplified version shows structure. Real implementations require careful bit level power computation.

```python id="q7m3te"
def powersort(a):
    n = len(a)
    stack = []

    def detect_run(i):
        j = i
        while j + 1 < n and a[j] <= a[j + 1]:
            j += 1
        return (i, j)

    def compute_power(l, r):
        mid = (l + r) // 2
        return mid.bit_length()

    def merge(l1, r1, l2, r2):
        temp = []
        i, j = l1, l2

        while i <= r1 and j <= r2:
            if a[i] <= a[j]:
                temp.append(a[i])
                i += 1
            else:
                temp.append(a[j])
                j += 1

        while i <= r1:
            temp.append(a[i])
            i += 1

        while j <= r2:
            temp.append(a[j])
            j += 1

        for k, v in enumerate(temp):
            a[l1 + k] = v

        return (l1, r2)

    i = 0
    while i < n:
        l, r = detect_run(i)
        p = compute_power(l, r)

        while stack and stack[-1][2] >= p:
            l1, r1, _ = stack.pop()
            l2, r2 = l, r
            l, r = merge(l1, r1, l2, r2)
            p = compute_power(l, r)

        stack.append((l, r, p))
        i = r + 1

    while len(stack) > 1:
        l1, r1, _ = stack.pop()
        l2, r2, _ = stack.pop()
        l, r = merge(l2, r2, l1, r1)
        stack.append((l, r, 0))

    return a
```