Natural Runs Sort

Natural runs sort is an adaptive sorting method that first finds sorted subsequences already present in the input. These subsequences are called natural runs. The algorithm then merges the runs until the whole sequence is sorted.

You use it when input data often contains long ordered stretches.

Problem

Given an array ( A ) of size ( n ), sort it by exploiting existing non-decreasing regions.

A natural run is a maximal contiguous segment:

( A[l] \le A[l+1] \le \dots \le A[r] )

Algorithm

Scan the array from left to right. Each time a maximal sorted run is found, store it. Then repeatedly merge adjacent runs.

natural_runs_sort(A):
    runs = []

    i = 0
    while i < length(A):
        j = i
        while j + 1 < length(A) and A[j] <= A[j + 1]:
            j = j + 1

        runs.append(A[i:j + 1])
        i = j + 1

    while length(runs) > 1:
        next_runs = []

        for p in 0, 2, 4, ...:
            if p + 1 < length(runs):
                next_runs.append(merge(runs[p], runs[p + 1]))
            else:
                next_runs.append(runs[p])

        runs = next_runs

    return runs[0]

Example

Input:

( [1, 4, 6, 2, 3, 5, 0, 7] )

Natural runs:

Merge these runs until one sorted sequence remains:

( [0, 1, 2, 3, 4, 5, 6, 7] )

Correctness

Every detected run is sorted by construction. Merging two sorted runs produces a sorted run containing exactly the elements of both inputs. Repeating this process preserves all elements and increases the size of sorted runs. When only one run remains, it contains every input element in sorted order.

Complexity

Let ( r ) be the number of natural runs.

Space:

( O(n) )

because merging usually uses an auxiliary buffer.

Stability

Natural runs sort is stable if the merge operation is stable. When equal elements appear in two runs, the element from the left run should be copied first.

if left[i] <= right[j]:
    output.append(left[i])
else:
    output.append(right[j])

When to Use

Natural runs sort is useful when:

• input is partially sorted
• data was produced by appending sorted batches
• stable sorting is required
• best case linear behavior matters

This idea is central to adaptive merge based sorts such as Timsort.