以前、ブロックソーティングでN*2+αでソートできる方法について興味有る方いらしたのと、
それを思いついたのでフローだけ書いておきます。
できたら報告ください。これは、問題では無いです。

リングバッファとソートバッファを用意します。
リングバッファにはデータを。ソートバッファには０〜Nの1刻みの数字で初期化します。
ソートバッファは、リングバッファのインデックスの列です。

それで、リングバッファのi番目の列とj番目の列を比較できるようにします。
comp(ring,Sort[i],Sort[j])>0;的な
リングバッファの方は絶対改変しませんので、安心して比較できます。
それを使ってソートしましょう。
比較後交換されるデータはソートバッファの方です。
if(IsSwap) std::swap(Sort[i],Sort[j]);
まぁ、俺の実力ではコムソート位が限界なのでコムソートを実装します。
それで、Ring[Sort[i]-1]がソート後のほしいデータ列です。
ソートバッファの中の0が先頭です。ソートバッファの0があるインデックスを返しましょう。

と、言うものですが、ドウでしょうか。