# Sliding Window Sort

# Sliding Window Sort

Sliding window sort maintains the elements inside a fixed-size moving window in sorted order. As each new element arrives, the oldest element leaves and the new element enters.

You use it when sorted queries are needed over recent data, not over the full stream.

## Problem

Given a stream ( x_1, x_2, \dots ) and a window size ( w ), maintain a sorted view of the active window:

[
[x_{t-w+1}, \dots, x_t]
]

after each new element arrives.

## Algorithm

Use a balanced multiset or balanced binary search tree.

For each new element:

1. Insert the new value
2. Remove the expired value if the window is larger than ( w )
3. Read the sorted order from the tree when needed

```id="v7m2q8"
sliding_window_sort(stream, w):
    window = queue()
    tree = balanced_multiset()

    for x in stream:
        window.push_back(x)
        tree.insert(x)

        if length(window) > w:
            old = window.pop_front()
            tree.remove_one(old)

        output tree.in_order()
```

## Example

Stream:

[
[4, 1, 5, 2, 3]
]

Window size:

[
w = 3
]

Sorted windows:

| step | active window | sorted view |
| ---- | ------------- | ----------- |
| 1    | [4]           | [4]         |
| 2    | [4, 1]        | [1, 4]      |
| 3    | [4, 1, 5]     | [1, 4, 5]   |
| 4    | [1, 5, 2]     | [1, 2, 5]   |
| 5    | [5, 2, 3]     | [2, 3, 5]   |

## Correctness

The queue stores the active window in arrival order. The balanced multiset stores exactly the same elements in sorted order.

Each update inserts the new value and removes the expired value. Therefore, after every step, the tree contains exactly the current window. An in-order traversal of the tree gives the sorted window.

## Complexity

| operation                 | cost          |
| ------------------------- | ------------- |
| insert                    | ( O(\log w) ) |
| delete expired value      | ( O(\log w) ) |
| output full sorted window | ( O(w) )      |

Space:

[
O(w)
]

## Duplicate Values

Use a multiset or store counts per value.

```id="h3c9x2"
insert(x):
    count[x] = count[x] + 1

remove_one(x):
    count[x] = count[x] - 1
    if count[x] == 0:
        delete x
```

## When to Use

Use sliding window sort when:

* only recent elements matter
* sorted window queries are frequent
* the stream is too large to store fully
* duplicates must be handled correctly

For median queries, use two heaps or an order statistic tree instead of outputting the full sorted window.