プログラミングお遊戯 〜std::minmax_element を使用したソート

επιστημηさんの『わすれもので(ちょびっと)高速化』に挑戦！
掲載のサンプルをビルドして Core i7 で実行すると...

• 359 (min_selection)
• 421 (minmax_selection)

んー。ご本人の環境では高速化が確認されたようですが、私の環境だと minmax_element が速くないように見えてしまいます。
…が、よくコードを見てみると、ソート対象の集合を削除しながら、ソート済みの集合を 2 つ作って最後にマージしてます。minmax_element に問題があるのではなく、周辺のコードに問題がありそうです。最近、案件でメモリアクセスの最適化関連に従事しているので、ちょっと気になるコードです。ご本人もコメントしてますが、かなりリッチな富豪的アプローチという雰囲気。
書き直してみました。

DWORD minmax_selection_sort2(list<int>& data) {
  DWORD t = GetTickCount();
  auto first = data.begin();
  auto end = first;  advance(end, data.size() - 1);
  auto end1 = data.end();
  while (first != end1) {
    auto mm_pair = minmax_element(first, end1);
    if (mm_pair.first == mm_pair.second) {
      break;
    }
    end1 = end;
    iter_swap(first, mm_pair.first);
    iter_swap(end, first != mm_pair.second ? mm_pair.second : mm_pair.first);
    ++first, --end;
  }
  return GetTickCount() - t;
}

集合を新たに作成することなく、ソート対象の集合を直接書き換えています。挿入ソートの場合、こうしたアプローチの方が一般的なように思います。結果は...

• 359 (min_selection)
• 421 (minmax_selection)
• 343 (minmax_selection2)

多少、速くなりました。1 割には満たないようですが、もうちょっと良いやり方があるのかな。
（補足）
計測に GetTickCount API 使ってますが、経験的に timeBeginPeriod, timeGetTime API が使える環境ならそちらの方がタイマーとしては安定した値が取得できると思います。