Adaptive Merge Sort

Adaptive merge sort improves standard merge sort by detecting existing order in the input. Instead of blindly splitting into fixed halves, it identifies already sorted subsequences called runs and merges them.

You use it when the input often contains partial order.

Problem

Given an array ( A ) of size ( n ), sort it while taking advantage of any existing sorted segments.

Idea

If the array already contains sorted runs, merging them directly costs less than recursively splitting everything.

Example:

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

Runs:

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

Instead of full recursion, detect these runs and merge them.

Algorithm

1. Scan the array and detect maximal non-decreasing runs
2. Push runs into a stack
3. Merge runs according to size rules to maintain efficiency

adaptive_merge_sort(A):
    runs = []

    i = 0
    while i < n:
        j = i
        while j + 1 < n and A[j] <= A[j+1]:
            j = j + 1

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

    while length(runs) > 1:
        left = runs.pop(0)
        right = runs.pop(0)
        runs.append(merge(left, right))

    return runs[0]

Example

Input:

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

Runs:

• ( [2, 4, 6] )
• ( [1, 3, 5] )

Merge:

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

Correctness

Each detected run is already sorted. Merging two sorted sequences produces a sorted result. Repeated merging eventually yields a fully sorted array.

Complexity

Space:

( O(n) )

Practical Notes

Real implementations, such as Timsort, refine this idea:

• enforce minimum run sizes
• use insertion sort for small runs
• apply merge policies to avoid imbalance

When to Use

Adaptive merge sort is useful when:

• data is partially sorted
• runs naturally occur (logs, time series, appended data)
• stability is required

It forms the basis of modern production sorting algorithms.