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

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:

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

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.