- 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

A comparison network that can sort all binary inputs correctly can sort any input correctly

Using the following

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.

\]

\begin{align}

G(n) &= 2G(\frac{n}{2}) + O(\frac{n}{2}log \;n) \\

\implies G(n) &= O(n \; log^2 \; n)

\end{align}

- 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:**

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}

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.**