Sorting Network

- A basic comparator
- Comparison network
- Depth of a sorting network
- Sorting network for insertion sort - $O(n^2)$ gates and $2n-1$ time units to sort n numbers

Zero-One Principle
A comparison network that can sort all binary inputs correctly can sort any input correctly
Proof:
Using the following lemma -
If a comparison network transforms input sequence $<a_1,\cdots ,a_n>$ to $<b_1,\cdots ,b_n>$, then for any monotonically increasing function $f$, the comparison network would transform $<f(a_1),\cdots , f(a_n)>$ to $<f(b_1),\cdots , f(b_n)> $

Given a sorting network with $n$ inputs which sorts all binary strings of length $2^n$ correctly, we need to show that it sorts all sequences correctly. We prove this by contradiction.

Let the network sort $a_1, \cdots, a_n$ incorrectly, i.e, $\exists \; a_i, a_k$ such that $a_i < a_k$ but $a_k$ proceeds $a_i$ in the output sequence (sorting being in ascending order). We define a monotonically increasing function $f$ as follows

\[
f(x) = \left\{
\begin{array}{ll}
0 & x\leq a_i \\
1 & x>a_i \\
\end{array}
\right.
\]

Now using the above lemma if the input is a binary string defined by $<f(a_1),\cdots , f(a_n)>$, then the output string would also be a binary string but with $f(a_k)$ appearing before $f(a_i)$. This is a contradiction to our hypothesis that the network sorts every binary string correctly. 

Hence proved by contradiction.

Definition: Bitonic Sequence

A sequence which first increases and then decreases or can be converted to such form by circular shifting. A binary bitonic sequence is either of the form $0^i1^j0^k$ or $1^i0^j1^k$

Definition: Half Cleaner

A comparison network which connects $i^th$ line with $(i+\frac{n}{2})^th$ line. For binary bitonic sequences it results in two possible cases:

- Top $\frac{n}{2}$ is $0$s and bottom half is a bitonic sequence

- Bottom $\frac{n}{2}$ is $1$s and top half is a bitonic sequence

Note- This provides a recursive way of sorting binary bitonic sequences. Also given two sorted sequences, a bitonic sequence can be easily obtained by flipping and concatenating the second sequence to the first sequence. This gives us the construction of Merge network whose components are listed below.  

Sorting Network

- Sort top $\frac{n}{2}$

- Sort bottom $\frac{n}{2}$

- Merge

      - Flip-Cleaner$[n]$

      - Top Bitonic Sorter$[n]$

      - Bottom Bitonic Sorter$[n]$

Number of Comparators required in Merge Circuit: $O(\frac{n}{2}log \;n)$

Number of Comparators required in the sorting network:

\begin{align}
G(n) &= 2G(\frac{n}{2}) + O(\frac{n}{2}log \;n) \\
\implies G(n) &= O(n \; log^2 \; n)
\end{align}

Depth of Merge Circuit: $O(log\; n)$

Depth of sorting network:

\begin{align}
D(n) &= D(\frac{n}{2}) + O(log\; n) \\
\implies D(n) &= O(log^2 \; n)
\end{align}

Yeah!! This is significantly better than $O(n \; log \; n)$ time taken by programmatic sorting algorithms.