algorithm の std::sort を使うとか？
いちおうO(log(n))でソートしてくれるはず…。

それで処理時間不足なら、もっと根本的な部分にトリックを入れないと。