マージソート

Erlang

Erlangを触っている。関数型ということもあって、C/C++では簡単に書けるものがどうやって書くのか、これで高速に動くのかなど頭を悩ませている。
なので練習がてらにマージソートを書いた。

//マージソート本体
mergeSort(L)->
    {Result,_} = mergeSort(1,[],L),
    Result.

mergeSort(_,Temp,[])->
    {Temp,[]};
mergeSort(0,Temp,[H|T])->
    {lists:merge(Temp,[H]),T};
mergeSort(Size,[],[H|T]) ->
    mergeSort(Size,[H],T);
mergeSort(Size,Temp,L) ->
    {Mid,Rest}=mergeSort(Size-1,[],L),
    mergeSort(Size+1,lists:merge(Temp,Mid),Rest).

効率的に書けないかと思ったらこんな風になった。なんていうかアッカーマン関数みたい。
イメージとしては、前から順にソートしていっている。つまり

リスト  [9   2   4   6   1   3   7]
         <-1->   <-2->   <-4->  <5>
         [2,9]   [4,6]   [1,3]  [7]
         <-----3----->   <---6---->
           [2,4,6,9]      [1,3,7]
         <-------------7---------->
               [1,2,3,6,7,9]
<>の中の数字の順にマージされていく。

実行結果
21> pytag:mergeSort([7,3,1,7,3,2,3,8,5]).
[1,2,3,3,3,5,7,7,8]

なるべく前の要素からアクセスできていると思う。うーん、これでいいのか？
リスト操作のオーバーヘッドどのくらいかかるのだろうか？もし、十分に早ければ
こんなことしなくてよさそう。

Erlang Performance
http://lab.klab.org/wiki/Erlang_Performance
Erlangでソートの速さの実験をしているのを見つけた。ソースコードを真似して実験してみる。
普通の分割してマージしていくものと比べてみると、

普通のマージソート上、作った方下
n=   10     100      1000      10000       100000
      1       1         1      47000       437000 (usec)
      1       1     31000    2153000        ----  (usec)

すげー遅い・・・(T.T)
O(nlogn)だから、データが10倍増えると10倍ぐらい遅くなるはず?

結論としては、普通にやった方が簡単だし速いということで、無駄なことをしまくっているのか。リスト操作関数を使うべきだ。関数呼び出しの回数やパターンマッチの回数が大きく影響しているのか?それとも、根本的にダメなのか。
どうもリスト操作が遅いのではないか？という固定観念があったが素人が頭使うよりシステムのほうが信用できそう