`xs`

and write the results into an array `ys`

.
In both cases, the invariant to be satisfied is that `ys`

is `xs`

in ascending
order. I'll be considering two broad ways to implement such a thing:
- 1.
Index straight into*(RANK)*`ys`

, reindexed into`xs`

. We name the reindexingarray as`rs`

(`rs`

for*ranks*).

```
for(int i = 0; i < N; ++i) {
ys[rs[i]] = xs[i]
}
```

- 2.
Reindex into*(SELECT)*`ys`

, index straight into`xs`

. We name the reindexing array`ss`

(`ss`

for*selects*).

```
for(int i = 0; i < N; ++i) {
ys[i] = xs[ss[i]]
}
```

`e`

is the number of elements that are:
- less than
`e`

. - equal to
`e`

but occur before`e`

.

`e`

is given
a ```
int rank(const int *xs, int i) {
int cnt = 0;
for (int j = 0; j < N; ++j) {
if (xs[j] < xs[i] || (xs[j] == xs[i] && j < i)) cnt += 1;
}
return cnt;
}
for(int i = 0; i < N; ++i) {
rs[i] = rank(xs, i);
}
```

`(xs[i], i)`

using lex ordering. So if two indeces
`i, j`

have the same value, then we sort on the index.
```
int rank(int *xs, int i) {
int cnt = 0;
for (int j = 0; j < i; ++j) {
if (xs[j] <= xs[i]) cnt += 1
}
return cnt;
}
```

I declined from doing so because I wanted to show the lex-ordering
interpretation of `rank`

will be be useful later.
- 1. From definition of rank:

```
ys[rs[i]] = xs[i]
```

- 2. move
`i -> ss[i]`

where`ss[i]`

is guaranteed to be a permutation,so we will write each index eventually:

```
ys[rs[ss[i]]] = xs[ss[i]]
```

- 3. Stipulate that
`rs[ss[i]] = i`

, since we want a`ys[i]`

:

```
ys[i] = xs[ss[i]]
```

This gives us necessary and sufficient conditions on how to find an `ss`

:
`ss`

must be a permutation that is an inverse permutation to `rs`

.
`rs[i]`

that maps
`i`

to `rs[i]`

. We want to find a new permutation `ss[i]`

such that
```
rs[ss[i]] = i
```

Equivalently:
```
// ss[i] is an index 'k'...
ss[i] = k
// 'k' is the location of 'i' in rs.
rs[k] = i
```

So if we first tag each location of `rs`

with its index, and then sort
with the values of `rs`

being the keys, then `ss[i]`

will be the values.
In pictures:
```
rs[i] [3 4 0 1 2]
rs_tagged[i] [(3, 0) (4, 1) (0, 2) (1, 3) (2, 4)]
rs_sorted[i] [(0, 2) (1, 3) (2, 4) (3, 0) (4, 1)]
ss[i] [ 2 3 4 0 1 ]
rs[ss[i]] [ rs[2] rs[3] rs[4] rs[0] rs[1]]
rs[ss[i]] [ 0 1 2 3 4 ]
```

- Rank starts with
`r`

and select starts with`s`

so we get nice naming. - Rank and select are true inverse permutations of each other.

- Richard Bird: Pearls of functional algorithm design