Merge Insertion Sort

Merge insertion sort is a comparison efficient sorting algorithm. It aims to minimize the number of comparisons, approaching the theoretical lower bound for comparison sorting.

It combines ideas from merge sort and insertion sort, but with a carefully designed insertion schedule that reduces comparisons.

It is mainly of theoretical interest and is rarely used in practice due to complexity and overhead.

Problem

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

Idea

The algorithm proceeds in stages:

1. pair elements and compare within each pair
2. recursively sort the larger elements of each pair
3. insert the smaller elements into the sorted sequence using binary insertion

The key improvement comes from controlling the order in which elements are inserted, reducing total comparisons.

Algorithm

merge_insertion_sort(A):
    if length(A) <= 1:
        return A

    pair elements into (a_i, b_i) with a_i <= b_i

    sort all b_i recursively

    insert each a_i into sorted b_i sequence
    using binary insertion in a specific order

The insertion order follows a carefully chosen sequence (often related to Jacobsthal numbers) to minimize comparisons.

Example

Let:

Pair and order:

• (2, 5)
• (3, 8)

Sort larger elements:

Insert smaller elements:

• insert 2 → [2, 5, 8]
• insert 3 → [2, 3, 5, 8]

Final result:

Correctness

Each pair is ordered locally. The recursive sort ensures that all larger elements are sorted. Inserting the smaller elements into this sorted structure produces a globally sorted array. The insertion process preserves order because it uses binary search to place each element correctly.

Complexity

The number of comparisons is close to the lower bound:

which is the minimum required by any comparison sort.

Properties

Notes

Merge insertion sort is also known as Ford Johnson sort. It is important in the study of optimal comparison sorting.

Despite its theoretical strength, it is rarely used in real systems because:

• it has high constant factors
• implementation is complex
• modern algorithms like Timsort perform better in practice

Implementation

This simplified implementation demonstrates the structure. It does not include the optimal insertion schedule.

def merge_insertion_sort(a):
    if len(a) <= 1:
        return a

    pairs = []
    for i in range(0, len(a), 2):
        if i + 1 < len(a):
            if a[i] <= a[i + 1]:
                pairs.append((a[i], a[i + 1]))
            else:
                pairs.append((a[i + 1], a[i]))
        else:
            pairs.append((a[i], None))

    large = [p[1] for p in pairs if p[1] is not None]
    small = [p[0] for p in pairs]

    large = merge_insertion_sort(large)

    result = large[:]

    for x in small:
        insert(result, x)

    return result

def insert(arr, x):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    arr.insert(lo, x)