# Lazy Sort

# Lazy Sort

Lazy sort delays sorting until the program needs ordered output. Instead of immediately sorting every inserted element, it stores unsorted data and performs sorting only when a query requires order.

You use it when many updates happen before few sorted reads.

## Problem

Maintain a collection that supports:

* inserting elements
* requesting sorted output
* avoiding unnecessary sorting work when sorted output is never requested

## Idea

Keep inserted elements in an unsorted buffer. When sorted output is requested, sort the buffer. If more elements arrive later, mark the collection as dirty and sort again only when needed.

## Algorithm

```id="v6m9q2"
lazy_sort_collection:
    data = []
    sorted = false

insert(x):
    data.append(x)
    sorted = false

sorted_output():
    if not sorted:
        sort(data)
        sorted = true

    return data
```

## Example

Operations:

```id="g9p2x5"
insert(5)
insert(1)
insert(3)
insert(2)
sorted_output()
```

The first four operations do no sorting. The final query sorts once:

[
[1, 2, 3, 5]
]

If no sorted query occurs, sorting cost is never paid.

## Correctness

The collection stores every inserted element. When sorted output is requested, it checks whether the current data is already sorted. If not, it sorts all stored elements using a correct sorting algorithm.

Therefore every sorted query returns the complete collection in sorted order.

## Complexity

Let ( n ) be the number of stored elements.

| operation                              |                                                       cost |
| -------------------------------------- | ---------------------------------------------------------: |
| insert                                 |                                         ( O(1) ) amortized |
| first sorted output after updates      |                                            ( O(n \log n) ) |
| repeated sorted output without updates | ( O(1) ) to return cached data, or ( O(n) ) to copy/output |

Space:

[
O(n)
]

## Incremental Variant

A more refined lazy sort keeps a sorted base and an unsorted delta buffer.

```id="b8x1r7"
lazy_merge_sort_collection:
    sorted_base = []
    delta = []

insert(x):
    delta.append(x)

sorted_output():
    sort(delta)
    sorted_base = merge(sorted_base, delta)
    delta = []
    return sorted_base
```

This avoids re-sorting the whole collection after every batch of new inserts.

## When to Use

Use lazy sort when:

* inserts are frequent
* sorted reads are rare
* sorting may never be needed
* batching updates is acceptable

It is common in databases, caches, UI lists, and query engines where work can be deferred until observation.