# Ford Johnson Sort

# Ford Johnson Sort

Ford Johnson sort is a comparison efficient sorting algorithm that minimizes the number of comparisons. It is one of the best known algorithms in terms of comparison count and closely approaches the theoretical lower bound.

It refines merge insertion sort by carefully controlling the order of insertions using a specific sequence.

## Problem

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

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

## Idea

The algorithm works in three main steps:

1. pair elements and sort each pair
2. recursively sort the larger elements
3. insert the smaller elements into the sorted sequence using a special insertion order

The insertion order is crucial. It follows a sequence designed to minimize the number of comparisons, often based on Jacobsthal numbers.

## Algorithm

```text id="r7k3xp"
ford_johnson_sort(A):
    if length(A) <= 1:
        return A

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

    sort all b_i recursively

    insert a_i into sorted sequence
    following optimal insertion order
```

Insertion uses binary search, but the order in which elements are inserted ensures minimal total comparisons.

## Example

Let:

$$
A = [6, 2, 9, 3]
$$

Pair and order:

* (2, 6)
* (3, 9)

Sort larger elements:

$$
[6, 9]
$$

Insert smaller elements:

* insert 2 → [2, 6, 9]
* insert 3 → [2, 3, 6, 9]

Final result:

$$
[2, 3, 6, 9]
$$

## Correctness

Each pair is locally sorted. The recursive step sorts the larger elements globally. Inserting the smaller elements using binary search places them in correct positions relative to the sorted sequence. The insertion order preserves optimal comparison structure, ensuring correctness.

## Complexity

| metric      | value         |
| ----------- | ------------- |
| time        | $O(n \log n)$ |
| comparisons | near optimal  |
| space       | $O(n)$        |

The number of comparisons is close to:

$$
\lceil \log_2(n!) \rceil
$$

which is the theoretical lower bound.

## Properties

| property                  | value     |
| ------------------------- | --------- |
| stable                    | yes       |
| in-place                  | no        |
| comparison optimality     | very high |
| implementation complexity | very high |

## Notes

Ford Johnson sort is mainly of theoretical importance. It demonstrates how to approach the lower bound on comparison sorting.

In practice, the algorithm is rarely used because:

* it is difficult to implement
* it has large constant overhead
* modern hybrid algorithms outperform it on real data

It remains important in algorithm theory and analysis of optimal comparison strategies.

## Implementation

This simplified version illustrates the structure but does not implement the optimal insertion schedule.

```python id="t3k8xp"
def ford_johnson_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 = ford_johnson_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)
```