# Coordinate Compression Sort

# Coordinate Compression Sort

Coordinate compression sort maps arbitrary values to a dense integer range based on their sorted order, then sorts using these compact indices. It is useful when values are large, sparse, or not directly suitable for counting or radix methods.

## Problem

Given an array $A$ of values, possibly large integers or non-integer comparable items, sort the array efficiently by reducing the value domain.

## Idea

Replace each value with its rank in the sorted order of distinct values.

Let:

$$
V = \text{sorted unique values of } A
$$

Define mapping:

$$
\text{rank}(x) = \text{index of } x \text{ in } V
$$

Then:

1. map each value to its rank
2. sort by ranks
3. optionally map back to original values

## Algorithm

```text id="k2p9qx"
coordinate_compression_sort(A):
    V = sorted unique values of A

    create map from value to index

    B = array of size n

    for i from 0 to n-1:
        B[i] = map[A[i]]

    sort B

    for i from 0 to n-1:
        A[i] = V[B[i]]

    return A
```

## Example

Let:

$$
A = [1000, 5000, 1000, 2000]
$$

Unique sorted values:

$$
V = [1000, 2000, 5000]
$$

Mapping:

| value | rank |
| ----- | ---- |
| 1000  | 0    |
| 2000  | 1    |
| 5000  | 2    |

Mapped array:

$$
[0, 2, 0, 1]
$$

Sorted:

$$
[0, 0, 1, 2]
$$

Mapped back:

$$
[1000, 1000, 2000, 5000]
$$

## Correctness

The mapping preserves order:

$$
x_1 < x_2 \iff \text{rank}(x_1) < \text{rank}(x_2)
$$

Thus sorting compressed values yields the correct order of original values.

## Complexity

Let:

* $n$ be number of elements
* $u$ be number of distinct values

Time:

* building $V$: $O(n \log n)$
* mapping: $O(n)$
* sorting compressed array: $O(n \log n)$

Total:

$$
O(n \log n)
$$

If combined with counting or radix sort after compression:

$$
O(n + u)
$$

Space:

$$
O(n + u)
$$

## Properties

| property             | value                      |
| -------------------- | -------------------------- |
| stable               | depends on underlying sort |
| in place             | no                         |
| comparison based     | partly                     |
| handles large values | yes                        |

## When to Use

Use coordinate compression when:

* values are large or sparse
* you want to apply counting or radix sort afterward
* relative ordering matters but exact values are not needed during sorting

Avoid when:

* values are already small integers
* direct sorting is simpler

## Implementation

```python id="x8q2mp"
def coordinate_compression_sort(a):
    if not a:
        return a

    vals = sorted(set(a))
    rank = {v: i for i, v in enumerate(vals)}

    comp = [rank[x] for x in a]
    comp.sort()

    return [vals[i] for i in comp]
```