<p>Suppose you have $n$ numbers $x_1,\ldots,x_n$ of width $m \geq \log n$. Without loss of generality, all numbers are different (add an extra $\log n$ lower-order bits). Two numbers can be compared in AC<sup>0</sup>, so in AC<sup>0</sup> we can compute, for each $x_i$, a binary vector $v$, defined by $v_j = 1$ if $x_j \geq x_i$. In TC<sup>0</sup> we can sort $v$ to $w$, and then locate (in AC<sup>0</sup>) the position $k$ such that $w_k = 1$ while $w_{k-1} = 0$ (where $w_0=0$, $w_{n+1}=1$). Given these values $k$ for each $i \in [n]$, we can compute the sorted array in AC<sup>0</sup>. In total, we get a TC<sup>0</sup> circuit.</p>

CC BY-SA 3.0
2012-10-17T15:36:09.243Z
nice trick :) (count the number of smaller numbers in the array), thanks Yuval.
Kaveh
CC BY-SA 3.0
2012-10-17T05:12:22.547Z
2012-10-17T05:12:22.547Z
Yuval Filmus
<p>It is not difficult to show that sorting an array of numbers is hard for $\mathsf{TC^0}$. 
If the input is an array of 1s and 0s then it is essentially the function $Count$ (given $n$ bits, output the number of 1s in binary) since $Count$ is complete for $\mathsf{TC^0}$ and it is possible to convert unary numbers to binary numbers and (logarithmicly) small binary numbers to unary numbers in $\mathsf{AC^0}$:</p>

<blockquote>
  <p>$Count(\vec{x}) = Binary(Sort(\vec{x}))$<br>
  $Sort(\vec{x}) = Unary(Count(\vec{x}))$</p>
</blockquote>

<p>So the power of $\mathsf{TC^0}$ is essentially sorting a binary string (eg. 100011 to 000111).
This is true more generally when the numbers in the array are bounded. My question is what if the numbers are not bounded? </p>

<p>Is the problem of sorting an array of unbounded numbers still in $\mathsf{TC^0}$?  Is it  complete for a larger class like $\mathsf{NC^1}$?</p>

CC BY-SA 3.0
2012-10-17T04:51:32.360Z
Btw, if you know a reference for "sorting arrays of bits is  $\mathsf{TC^0}$-complete" please let me know.
Kaveh
CC BY-SA 3.0
2012-10-17T05:11:16.417Z
Did you check Cook & Nguyen?
Yuval Filmus
CC BY-SA 3.0
2012-10-17T13:10:12.480Z
@Kaveh, the reduction is in Chandra, Stockmeyer and Vishkin, "Constant Depth Reducibility", SIAM J. Comput. 13 (2), 1984.
Jan Johannsen
<cc.complexity-theory><circuit-complexity><sorting>
Complexity of sorting
Kaveh
# Complexity of sorting

(Asked by: username_0 on 2012-10-17)

It is not difficult to show that sorting an array of numbers is hard for $\mathsf{TC^0}$.
If the input is an array of 1s and 0s then it is essentially the function $Count$ (given $n$ bits, output the number of 1s in binary) since $Count$ is complete for $\mathsf{TC^0}$ and it is possible to convert unary numbers to binary numbers and (logarithmicly) small binary numbers to unary numbers in $\mathsf{AC^0}$:

> $Count(\vec{x}) = Binary(Sort(\vec{x}))$  
> $Sort(\vec{x}) = Unary(Count(\vec{x}))$

So the power of $\mathsf{TC^0}$ is essentially sorting a binary string (eg. 100011 to 000111).
This is true more generally when the numbers in the array are bounded. My question is what if the numbers are not bounded?

Is the problem of sorting an array of unbounded numbers still in $\mathsf{TC^0}$? Is it complete for a larger class like $\mathsf{NC^1}$?

**Tags:** cc.complexity-theory, circuit-complexity, sorting

> **Comments:**
> **username_0**: Btw, if you know a reference for "sorting arrays of bits is  $\mathsf{TC^0}$-complete" please let me know.  
> **username_1**: Did you check Cook & Nguyen?  
> **username_2**: @username_0, the reduction is in Chandra, Stockmeyer and Vishkin, "Constant Depth Reducibility", SIAM J. Comput. 13 (2), 1984.  

---

## 1 answers

### Answer by username_1 on 2012-10-17. Score: 10 | Accepted answer

Suppose you have $n$ numbers $x\_1,\ldots,x\_n$ of width $m \geq \log n$. Without loss of generality, all numbers are different (add an extra $\log n$ lower-order bits). Two numbers can be compared in AC0, so in AC0 we can compute, for each $x\_i$, a binary vector $v$, defined by $v\_j = 1$ if $x\_j \geq x\_i$. In TC0 we can sort $v$ to $w$, and then locate (in AC0) the position $k$ such that $w\_k = 1$ while $w\_{k-1} = 0$ (where $w\_0=0$, $w\_{n+1}=1$). Given these values $k$ for each $i \in [n]$, we can compute the sorted array in AC0. In total, we get a TC0 circuit.

> **Comments:**
> **username_0**: nice trick :) (count the number of smaller numbers in the array), thanks Yuval.  

---

