It's possible to encode a version of *Bubble Sort* by hand, that be shown to correctly sort numbers in $O(n^2)$ time.

Bubble Sort proceeds by flipping adjacent elements of the array which are inverted. For example,

```
  3   2   1
    x
  2   3   1
        x
  2   1   3
    x
  1   2   3
```

This can be implemented with a double for loop
```
for i in 0..n {
  for j in i+1..n {
    if arr[i] > arr[j] {
       arr[i], arr[j] = arr[j], arr[i];
    }
  }
}
```

### Swap Layers

To begin, we will design a swap layer which can swap adjacent elements to correct their order. One swap layer is equivalent to one outer loop iteration of the above pseudocode.

Let $X_i$ be the input vector encoded as floats. The swap layer $Y_i$ has the same size as the input. All equations are written with $0$ based indexing.

$$
Y_i = 
\begin{cases}
  min(X_i, X_{i+1}) & \text{if $i$ is even} \\
  max(X_i, X_{i-1}) & \text{if $i$ is odd} \\
\end{cases}
$$

The odd case needs a max pool followed by transposed convolution that pads a zero on the left.

```
   3 2 1
    \|
=>   3   (Max Pool)
=> 0 3 0 (Padding)
```

The even case is just a min pool (explained later) followed by a transposed convolution layer that pads the input with 0 on the right,

```
    3 2 1
    |/ \|
 => 2   1 (Min Pool)
 => 2 0 1 (Zero padding)
```

The two pools are then summed to produce a swap layer. Summing can be done with a simple 1x1 conv layer with stride 1.

```
  0 3 0
+ 2 0 1
 -------
= 2 3 1
```

The overall structure of a swap layer looks like this,

```
Input --> MinPool -- Zero pad-- + --> Swapped
   |                            |
   |----> MaxPool -- Zero pad --|
```

Stacking $n$ swap layers, would sort the array. 

The min pool can be implemented with 2 1x1 convolution layers with linear activations and 1 max pool in between since, 

$$min(a, b) = -max(-a, -b)$$

Linear activations will not work for negative numbers but you can use ReLU if you assume that a large positive number has been added to the input via the bias and then subtracted at the output with another layer.

Thus, sorting can be done with $O(n)$ layers with $n$ neurons each.