Two parts of TCS are algorithms and complexity. I'll simplistically say that algorithms is the study of upper bounds, showing that you can do something (with given restricted resources), and complexity is about showing that you cannot do it without some minimal resources.So often an algorithmic problem is stated in a decision model in order to place it in a complexity class.But something that's always bothered me is that some elementary algorithms are never mentioned outright as belonging to a particular class. One example is (comparison) sorting. Try as I might, a relevant class just seems too deficient (really, is it just checking in logspace that the result is sorted? That just seems too weak, or I'm not getting the decision version right).What is the best/most appropriate/most useful complexity class that comparison sorting lies in?
Complexity class corresponding to sorting
cc.complexity theory;sorting
The sorting problem is actually complete for $\mathsf{TC}^0$ (under $\mathsf{AC}^0$-reduction). A standard source for this is Section 1.4.3 of Vollmer's book. Note that $\mathsf{TC}^0$ is the class of decision problems, but we usually think of sorting as a function problem, i.e., we want to output the numbers, say, in nondecreasing order. However, we can also define sorting as a decision problem as follows:Given a sequence of numbers $a_1,\ldots,a_n$ and two numbers $k,p\in [n]$, we want to decide if $a_k$ is at position $p$ in the sequence we get by sorting $a_1,\ldots,a_n$ in nondecreasing order. Note that to avoid ambiguity, when $a_i=a_j$, we want $a_i$ to precede $a_j$ if $i<j$.