Adaptive Shivers Sort

Adaptive Shivers sort is a run-based merge sort that improves how runs are merged. It detects natural runs and applies a stack discipline with carefully chosen merge rules to keep merges balanced.

You use it when input contains natural runs and you want tighter control over merge cost than simple strategies.

Problem

Given an array ( A ), sort it by:

• detecting natural runs
• merging them in an order that minimizes total merge work

Idea

Like Timsort, Shivers sort builds a stack of runs. The difference lies in stricter merge rules that consider run lengths more precisely.

Runs are merged when certain size relations are violated. These rules prevent very unbalanced merges, which would increase total work.

Algorithm

adaptive_shivers_sort(A):
    stack = []
    runs = detect_runs(A)

    for run in runs:
        stack.push(run)

        while need_merge(stack):
            r2 = stack.pop()
            r1 = stack.pop()
            merged = merge(r1, r2)
            stack.push(merged)

    while length(stack) > 1:
        r2 = stack.pop()
        r1 = stack.pop()
        stack.push(merge(r1, r2))

    return stack[0]

Merge Condition

A typical rule uses run lengths:

Let top runs be ( X, Y, Z ) (from bottom to top). Merge when:

• ( |X| \le |Y| + |Z| ), or
• ( |Y| \le |Z| )

These conditions enforce balanced merges.

Example

Input:

[ [1, 2, 5, 3, 4, 8, 6, 7] ]

Detected runs:

• [1, 2, 5]
• [3, 4, 8]
• [6, 7]

Stack evolves and merges based on size rules, avoiding merging a very large run with a tiny one.

Correctness

Each run is sorted. Merge operations combine two sorted runs into a sorted result. The stack rules only control merge order, not correctness.

At the end, all runs are merged into one sorted sequence.

Complexity

Space:

[ O(n) ]

Comparison with Timsort

When to Use

Adaptive Shivers sort is useful when:

• input has natural runs
• merge cost needs tight control
• worst-case guarantees matter
• you want a principled alternative to heuristic merge policies

It is mainly studied in algorithm theory and advanced sorting research.