パフォーマンスには一家言ある私ですが、さすがに1GBのintのソート時間にはピンと来ませんでした。
という訳で、ホントかどうかやってみました。
#include <vector>
#include <algorithm>
#include <iostream>
#include <time.h>
using namespace std;
int main(void)
{
vector<int> values;
srand(time(0));
// vectorに適当な値を入れる
for ( int i = 0; i < 1024*1024*1024 / sizeof(int); i++ ) {
values.push_back((int)(rand()*rand()-i));
}
// ソートする
clock_t t = clock();
sort( values.begin(), values.end());
cout << "Time(sort) is "
<< (double)(clock() - t) / CLOCKS_PER_SEC << "sec." << endl;
return 0;
}
実行時間（Core i7-920 Windows7 コンパイルVC++2008 リリースモード 64ビットモード）は以下になります。上記のプログラムですが、32ビットモードでは動作しません。32ビットプロセスはリニアに1GBのメモリは確保できないです。
Time(sort) is 43.895sec.
なるほど、確かに30秒からそう離れていません。
ちなみに、この手の封筒の裏計算ですが、桁が違わなければOKと考えてよいでしょう。なので、細かい値の違いが問題になる場合は、実アプリでキチンとベンチマークをとるのがよいでしょう。
この手の結果の受け止め方ですが、おそらく一般の業務アプリを作成する人にとっては『理論的限界値』程度に思っていた方がよいでしょう。つまり
1秒間に数百万個のint型のソートができる。数千万個になったら要注意。
と思っておけばよろしいかと思います。実際に私の経験でも行数が数百万件のソートをSQLで行うのはあまり問題になることはなかったです。（もちろんメモリが十分にあればの話ですが）。
実行時間の詳細ですが、説明では以下のとおりでした。
・要素を比較する回数（ソートのオーダnlogn）から、
2^28 * log(2^28) → 2^28 * 28 → 2^28 * 2^5 → 2^33(2の33乗)回
・比較に際してのL1キャッシュのアクセス時間 0.5ns / 回
・比較に際してのブランチペナルティ 2.5ns / 回（2回に1回ペナルティがあると仮定する）
実行時間 2^33 * (0.5 + 2.5)nsec = 25.76sec 約30秒
ただ、上記の計算ですが、ブランチペナルティが全体の速度を決定しているというのはいささか疑問があります。上記の場合、メモリのアクセス回数から計算した方が良いのでは？と思います。
つまり、
・要素を比較する回数（ソートのオーダnlogn）から、
2^28 * log(2^28) → 2^28 * 28 → 2^28 * 2^5 → 2^33（2の33乗）回
・ 比較に際してのメモリアクセス回数 2回（リード&ライト） 2*4バイト
・キャッシュライン 32バイト
・メインメモリへのアクセス回数 2^33 * 2 * 4 / 32 = 2^31 回
・メインメモリアクセス性能 1回のアクセス 10nsec（DDR3のレイテンシーから）
実行時間 2^31 * 10nsec = 21.47sec
うーん、数値的には似たり寄ったりであまり変わらないか・・・・