# Relations & Notation

Before getting too deep into how sorting works, I'm going to introduce
some new functions and convenience notation first. In the
first post in this series, we talked
about $\text{eq}$, which is a relation. A relation can be defined for
our needs as a function of two arguments that always evaluates to either
$0$ or $1$. That is, it is a function $f$ with the type signature
$$ f : \mathbb{R} \to \{0, 1\} $$
Other common relations can be defined as follows:
$$
\begin{aligned}
\text{lt}(x, y) &= \text{eq}(-1, \text{sign}(x - y)) \\
\text{gt}(x, y) &= \text{eq}(1, \text{sign}(x - y)) \\
\text{leq}(x, y) &= 1 - \text{gt}(x, y) \\
\text{geq}(x, y) &= 1 - \text{lt}(x, y)
\end{aligned}
$$
where the equations are `x < y`

, `x > y`

, `x <= y`

, and `x >= y`

, respectively.
"Calling" these relations each time get cumbersome, so we will be using a
notation inspired by the Iverson Bracket
for convenience. Instead of writing $\text{lt}(x, y)$, we will
write $[x < y]$. This extends to the other relations defined above.

Note: We will only use the Iverson bracket with comparison operators whose functions have been previously defined, so that we are always using only binary & elementary operations "under the hood".

# Sorting

## What do we mean by sorting?

Since the primary "data" that we are working with are integers, a sorting function would be one that sorts the digits within an integer. For example, $$ \text{sort}_{10}(31524_{10}) = 54321_{10} $$ The reason we sort in "decreasing" order is twofold: Since the digit at index $i = 0$ is the rightmost digit, sorting in this direction would mean that iterating from $i = 0$ to $\text{len}_b(x) - 1$ would traverse the digits in increasing order. Furthermore, we sort in this order to preserve $0$'s. If we sorted in the other direction, $1001$ and $101$ would look the same when sorted in base $10$, which is not a desirable quality.

## Implementation

Sorting follows pretty naturally after reversing. Reversing is simply taking every digit of a number and placing it at a new index. Sorting is the exact same thing, except that the function that decides the new indices is different. That is, $$ \begin{aligned} \text{sort}_b(x) = \sum_{i = 0}^{\text{len}_b(x) - 1} \text{at}_b(x, i) \cdot b^{\sigma(x, i, b)} \end{aligned} $$ where $\sigma(x, i, b)$ returns the new index of the digit at index $i$ of $x$ in base $b$. Notice this is exactly $\text{rev}$ when $$\sigma_{rev}(x, i, b) = \text{len}_b(x) - i - 1$$ Now, what would $\sigma_{sort}(x, i, b)$ be? A reasonable guess for would be the number of digits in $x$ less than $\text{at}(x, i, b)$. That is, $$ \begin{aligned} \sigma_{sort}(x, i, b) = \sum_{j = 0}^{\text{len}_b(x) - 1} [\text{at}_b(x, j) < \text{at}_b(x, i)] \end{aligned} $$ However, this doesn't work for numbers with duplicate digits, as this would send both instances of the digit $3$ in the number $1233$ to the same index.

What we ended up coming up with was this: $\sigma_{sort}$ would be the
number of digits in $x$ strictly less than $\text{at}_b(x, i)$
*plus* the number of instances of the digit $\text{at}_b(x, i)$ at
indices less than $i$. That is,
$$
\begin{aligned}
\sigma_{eq}(x, i, b) &= \sum_{j = 0}^{i - 1} [\text{at}_b(x, j) = \text{at}_b(x, i)] \\
\sigma_{lt}(x, i, b) &= \sum_{j = 0}^{\text{len}_b(x) - 1} [\text{at}_b(x, j) < \text{at}_b(x, i)] \\
\sigma_{sort}(x, i, b) &= \sigma_{eq}(x, i, b) + \sigma_{lt}(x, i, b)
\end{aligned}
$$
Now we can define $\text{sort}$ as,
$$
\begin{aligned}
\text{sort}_b(x) = \sum_{i = 0}^{\text{len}_b(x) - 1} \text{at}_b(x, i) \cdot b^{{\sigma_{sort}}(x, i, b)}
\end{aligned}
$$
An interesting side note here is that, in some sense, this sort is
stable.
Obviously integers that are equal are fungible. That is, every $1$
is the same as every other $1$ in the pool of integers $\mathbb{Z}$.
If equal digits were distinguishable, as they do in computers,
through their location in memory, then this sorting function would
be considered stable.

Similar to what we did in a previous post we can convert this definition to code. Here's an example in Python,

And again let's test it out to see if it works:

Sweet! Looks like we can sort integers now. Next we'll talk about making a Look and Say function $L(x)$, that takes in an integer $x$ and outputs the next term in the Look and Say sequence.