# Incremental Sort

# Incremental Sort

Incremental sort maintains a sorted structure as new elements arrive. Instead of sorting after all data is available, it updates order step by step.

You use it when data arrives over time or when intermediate sorted states are required.

## Problem

Given a stream or sequence ( A ), process elements one by one and maintain a structure such that:

* elements seen so far remain sorted
* insertion preserves order

## Algorithm (Insertion based)

Maintain a sorted array. Insert each new element into its correct position.

```id="k3f8s1"
incremental_sort(A):
    result = []

    for x in A:
        i = length(result) - 1
        result.append(x)

        while i >= 0 and result[i] > x:
            result[i+1] = result[i]
            i = i - 1

        result[i+1] = x

    return result
```

## Example

Input stream:

( [5, 2, 8, 1] )

Steps:

* insert 5 → [5]
* insert 2 → [2, 5]
* insert 8 → [2, 5, 8]
* insert 1 → [1, 2, 5, 8]

## Correctness

At each step, the prefix remains sorted. The insertion step places the new element into its correct position relative to all previously processed elements. By induction, the structure stays sorted after every insertion.

## Complexity

| operation         | cost       |
| ----------------- | ---------- |
| single insertion  | ( O(n) )   |
| total (n inserts) | ( O(n^2) ) |

Space:

( O(n) )

## Alternative Structures

You can improve performance using different data structures:

| structure         | insertion     | sorted iteration    |
| ----------------- | ------------- | ------------------- |
| array (insertion) | ( O(n) )      | ( O(n) )            |
| balanced BST      | ( O(\log n) ) | ( O(n) )            |
| heap              | ( O(\log n) ) | not sorted directly |

Balanced trees support faster insertion while preserving order.

## When to Use

Incremental sort is useful when:

* data arrives as a stream
* you need sorted output at intermediate steps
* input size grows gradually

For large static datasets, batch sorting methods are more efficient.