FlashSort実験

Flash sortやFlash sortで紹介されているFlashSortというアルゴリズムですが、The FlashSort AlgorithmからダウンロードしたJava版のソースコードにナイーブなQuickSortをくっつけて動かしてみると、

> java FlashSort 1000000
Partial flash sort time     : 250
Straight insertion sort time: 70
Naive quick sort time       : 291

> java FlashSort 5000000
Partial flash sort time     : 2043
Straight insertion sort time: 361
Naive quick sort time       : 1582

> java FlashSort 6000000
Partial flash sort time     : 2453
Straight insertion sort time: 431
Naive quick sort time       : 2023

> java FlashSort 7000000
Partial flash sort time     : 3094
Straight insertion sort time: 511
Naive quick sort time       : 2263

> java FlashSort 8000000
Partial flash sort time     : 3625
Straight insertion sort time: 581
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

という具合になりました。QuickSortとComparableだけど、そんなに速くない？？
実験したソースはいちおうここに置いておきます。
やり方がまずいとか、何か情報がありましたらご教示よろしくお願いします＞みなさま。
（まあ、特定の実装で走らせただけでアルゴリズムを比較するのは意味がないですけれど…）
（あ、でも比較してるし…）
追記:id:hiuchidaさんから、「java -Xint」だとNaive quicksortのほうが時間がかかるという情報をいただきました。ありがとうございます。
追記:Cでやってみたらやっぱりqsortのほうが速いという情報も。