配列の先頭の要素を常にピボットとするクイックソートで、時間計算量が最悪の $O(n^2)$ になるのは、どのような入力のときか。

解説

正解は「すでに昇順に整列されている」です。クイックソートは、ピボットより小さい要素と大きい要素に分割して再帰的に整列します。整列済みの配列で先頭をピボットにすると、ピボットが常に最小値となり、分割の一方が空、もう一方が残り全部になります。分割が n 段近く続き、各段で残りの要素と比較するので、比較回数は約 $n^2/2$ となり $O(n^2)$ です。「要素がランダムに並んでいる」場合は分割がほぼ均等になりやすく、平均 $O(n\log n)$ です。「全要素の中央値が先頭にある」と、最初の分割がほぼ半分ずつになり、むしろ理想的です。「要素の個数が2のべき乗である」ことは計算量に影響しません。