# Nearly Sorted Insertion Sort

# Nearly Sorted Insertion Sort

Nearly sorted insertion sort is ordinary insertion sort applied to input that is already close to sorted order. Insertion sort adapts well to this case because each element moves only a short distance.

You use it when the input has small disorder, such as data produced by appending a few new records, merging mostly ordered logs, or correcting a sequence after minor edits.

## Problem

Given an array ( A ) of length ( n ), sort it under the assumption that most elements are already near their final sorted positions.

A useful measure is the number of inversions. An inversion is a pair ( (i, j) ) such that:

[
i < j \quad \text{and} \quad A[i] > A[j]
]

Insertion sort runs quickly when the number of inversions is small.

## Algorithm

Scan from left to right. At each index, insert the current value into the already sorted prefix.

```id="a2x7m9"
nearly_sorted_insertion_sort(A):
    for i in 1..length(A)-1:
        x = A[i]
        j = i - 1

        while j >= 0 and A[j] > x:
            A[j + 1] = A[j]
            j = j - 1

        A[j + 1] = x

    return A
```

## Example

Input:

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

Only a few adjacent pairs are out of order. Insertion sort performs a small number of shifts:

| step | inserted | result                   |
| ---- | -------: | ------------------------ |
| 1    |        2 | [1, 2, 4, 3, 5, 7, 6, 8] |
| 2    |        4 | [1, 2, 4, 3, 5, 7, 6, 8] |
| 3    |        3 | [1, 2, 3, 4, 5, 7, 6, 8] |
| 4    |        5 | [1, 2, 3, 4, 5, 7, 6, 8] |
| 5    |        7 | [1, 2, 3, 4, 5, 7, 6, 8] |
| 6    |        6 | [1, 2, 3, 4, 5, 6, 7, 8] |

## Correctness

Before processing index ( i ), the prefix ( A[0..i-1] ) is sorted. The algorithm shifts all elements greater than ( A[i] ) one position to the right and places ( A[i] ) into the unique position that preserves sorted order.

By induction, the prefix remains sorted after every iteration. After the final iteration, the whole array is sorted.

## Complexity

Let ( I ) be the number of inversions in the input.

| input          | time         |
| -------------- | ------------ |
| already sorted | ( O(n) )     |
| nearly sorted  | ( O(n + I) ) |
| reverse sorted | ( O(n^2) )   |

Space:

[
O(1)
]

## Stability

The algorithm is stable when it shifts only elements strictly greater than the inserted value.

```id="t4u7b1"
while j >= 0 and A[j] > x:
```

Equal elements keep their original relative order.

## When to Use

Use nearly sorted insertion sort when:

* input is almost sorted
* changes since the last sorted state are small
* the array is small
* stable in-place sorting is useful

It is often used inside hybrid sorting algorithms for small runs or nearly ordered regions.