# Online Insertion Sort

# Online Insertion Sort

Online insertion sort is insertion sort used in an online setting. It accepts elements one at a time and keeps all seen elements sorted after each insertion.

You use it when the input is not available all at once, but the sorted prefix must remain queryable during processing.

## Problem

Given a stream of values ( x_1, x_2, \dots, x_n ), maintain a sorted sequence ( S ) after each new value arrives.

After processing ( x_i ), the structure should contain exactly:

( {x_1, x_2, \dots, x_i} )

in sorted order.

## Algorithm

Keep a sorted array. When a new value arrives, scan backward from the end, shift larger elements one position right, then place the new value into the opened position.

```id="33k2ah"
online_insertion_sort(stream):
    S = []

    for x in stream:
        S.append(x)

        i = length(S) - 2
        while i >= 0 and S[i] > x:
            S[i + 1] = S[i]
            i = i - 1

        S[i + 1] = x

        output S
```

## Example

Input stream:

( [4, 1, 6, 3] )

State after each insertion:

| step | inserted | sorted state |
| ---- | -------: | ------------ |
| 1    |        4 | [4]          |
| 2    |        1 | [1, 4]       |
| 3    |        6 | [1, 4, 6]    |
| 4    |        3 | [1, 3, 4, 6] |

## Correctness

Before inserting a new value ( x ), assume ( S ) is sorted. The algorithm shifts every element greater than ( x ) one position to the right and stops at the first element less than or equal to ( x ), or at the beginning. Placing ( x ) there preserves sorted order.

By induction over the number of processed elements, ( S ) is sorted after every insertion.

## Complexity

| case                  | insertion cost | total cost |
| --------------------- | -------------: | ---------: |
| best, already sorted  |       ( O(1) ) |   ( O(n) ) |
| worst, reverse sorted |       ( O(n) ) | ( O(n^2) ) |
| average               |       ( O(n) ) | ( O(n^2) ) |

Space usage is:

( O(n) )

because the algorithm stores all processed elements.

## Stability

Online insertion sort is stable when equal elements are not shifted past each other. The condition should be:

```id="7q23td"
while i >= 0 and S[i] > x:
```

not:

```id="39gejr"
while i >= 0 and S[i] >= x:
```

This preserves the original arrival order of equal values.

## When to Use

Online insertion sort is useful when:

* elements arrive over time
* the sorted state is needed after every insertion
* the sequence is small or nearly sorted
* stable ordering matters

For large streams, use a balanced search tree when full sorted iteration is needed, or a heap when only the minimum or maximum is needed.