= Solution
<Heapsort> uses $\Theta(n)$ time for <bottom-up heap construction> and $O(\log n)$ for each extraction, giving $\Theta(n\log n)$ worst-case <time complexity>. An iterative <heapify down> on an <array> uses $O(1)$ auxiliary <space complexity>. Ordinary <heapsort> is not a <stable sorting> method.
<Quicksort> has balanced-case and average-case $\Theta(n\log n)$ <time complexity> when the input order supplies suitably distributed pivot ranks. With the prescribed first-element pivot, sorted inputs produce subproblems of sizes $0$ and $n-1$, giving $T(n)=T(n-1)+\Theta(n)=\Theta(n^2)$. With the stated two-way partition convention, all-equal keys also give this worst case. There is no input-independent expected bound without a distribution or randomization assumption. For an in-place <array> implementation, the recursion stack is $O(\log n)$ when balanced and $O(n)$ in the worst case; the functional <list> trace also allocates new partition spines and copied concatenation prefixes. Ordinary in-place <quicksort> is not <stable sorting>; the stable-partition <list> convention used in the trace can preserve equal-key order at additional allocation cost.
<Counting sort> uses $\Theta(n+k)$ <time complexity> for $k$ possible consecutive <integer> keys. The <stable sorting> version uses $\Theta(n+k)$ auxiliary <space complexity> including the output <array>; counting and re-emitting bare keys needs only $O(k)$ beyond its output. It is attractive when $k$ is small, but a sparse huge key range makes both initialization and count storage expensive. It relies on indexing by bounded <integer> keys, so it is not subject to the <comparison sorting lower bound>.
$$
\boxed{\text{heapsort: }\Theta(n\log n);\quad
\text{quicksort worst case: }\Theta(n^2);\quad
\text{counting sort: }\Theta(n+k).}
$$
Back to article page
