# Order Maintenance Sort

# Order Maintenance Sort

Order maintenance sort maintains a total order of elements under dynamic insertions. Instead of re-sorting, it assigns labels that preserve relative order and supports fast comparisons.

You use it when elements are inserted over time and you need to maintain their sorted or logical order efficiently.

## Problem

Maintain a sequence that supports:

* inserting an element after another element
* comparing the order of two elements
* preserving total order without full re-sorting

## Idea

Assign each element a numeric label such that:

[
\text{label}(a) < \text{label}(b) \quad \Longleftrightarrow \quad a \text{ comes before } b
]

When inserting a new element between two existing ones, assign it a label between their labels.

If no space remains between labels, relabel a block.

## Algorithm

```id="k2m8x5"
order_maintenance:
    elements = linked list
    labels = map from element to number

insert_after(a, x):
    b = next(a)

    if label(a) + 1 < label(b):
        label(x) = (label(a) + label(b)) / 2
    else:
        relabel_block(a, b)
        label(x) = (label(a) + label(b)) / 2

    insert x after a in list
```

## Example

Initial:

| element | label |
| ------- | ----- |
| A       | 10    |
| B       | 20    |
| C       | 30    |

Insert ( X ) between A and B:

[
\text{label}(X) = 15
]

Updated order:

[
A, X, B, C
]

## Correctness

Labels preserve total order. Every insertion assigns a label strictly between its neighbors. If labels become too dense, relabeling restores spacing while maintaining relative order.

Thus comparisons using labels always reflect correct ordering.

## Complexity

| operation  | cost                     |
| ---------- | ------------------------ |
| insertion  | ( O(1) ) amortized       |
| comparison | ( O(1) )                 |
| relabeling | ( O(n) ) worst, but rare |

Space:

[
O(n)
]

## Variants

More advanced implementations use:

* balanced trees with implicit indexing
* packed memory arrays
* indirection to reduce relabel cost

These improve worst-case guarantees.

## Relation to Sorting

This method does not sort in the traditional sense. Instead, it maintains order incrementally. A full sorted sequence is always available by traversing the maintained structure.

## When to Use

Use order maintenance when:

* elements are inserted dynamically
* order queries are frequent
* full re-sorting is too expensive
* stable ordering must be preserved

It appears in text editors, version control systems, and incremental computation systems.