>>422
まずソートについて。

累積度数分布表が作れるようなデータ（つまり、０〜１００とかみたいに、
値の範囲が限られた整数になるデータ）では、累積度数分布表を作ってソート
するのがもっとも高速です。O(N)時間でソートできます。「度数ソート」
「分布数えソート」等で検索してください。

x%点について。累積度数がx%を超えるまで累積度数を計算し、その順位にある
データを見つければよいわけですが、
・度数分布…N回ループ
・累積度数…(xN/100)回ループ
・その順位のデータを見つける…(N/2)回ループ
で、まあ、何割か早くなるでしょうが、「度数ソートしてX番目」と
オーダーとしてはおんなじです。