中央値の中央値
つまり、ここでmを大きくして小配列の要素数を増やしたとしても、結局、次の探索対象の要素数は 3 4 n {\displaystyle {\frac {3}{4}}n} 個、つまり元の要素数の75%にしかならない。一方で小配列の中の要素数が増えていくと、分割処理にも小配列の中での中央値を探すのにも時間がかかるようになってしまい、元の配列の要素数が充分に大きくなると全体的な性能向上には寄与しなくなってしまう。
別の分割方法として、要素数が一定の小配列ではなく一定数の小配列に分割する、つまり、要素数が5個ずつの小配列ではなく、5個の小配列に分割することを考える。しかしその場合は、明らかに要素数は減少させることはできない。なぜなら、要素数 1 5 n {\displaystyle {\frac {1}{5}}n} 個ずつの小配列5個の中で、それぞれ中央値を計算せねばならないが、結局、次の探索対象の要素数は 7 10 n {\displaystyle {\frac {7}{10}}n} 個にしかならないからである。つまり、3要素ずつに分割する時と同様に、個々の中央値を計算する配列の要素数は元の配列より少なくて済むが、結局、全体的な長さは短くならず、むしろ長くなってしまう。要素数が n {\displaystyle {\sqrt {n}}} 個の小配列に分割しても、小配列の数は n {\displaystyle {\sqrt {n}}} 個になり、同様である。