またどう書くに投稿してみた

http://ja.doukaku.org/comment/6809/
かなりこれも恥ずかしい。本に書いてある通りのアルゴリズムではない(というか、本なんか読んでない)ので、テストはしてみたけど、証明済みではない。

　-module(sort).
　-export([main/4]).

main(Min, Max, _Num, List) ->
   sort(Min, Max, List).

sort(_Min, _Max, [ ] ) -> [ ] ;
sort(_Min, _Max, [H| [ ] ]) -> [H];
sort(Min, Min, List) -> List;
sort(Min, Max, List) ->
    Pivot = Min + ((Max - Min) div 2),
    sort(Min,Pivot, [ X || X <- List, X < Pivot ])
    ++
    [ X || X <- List, X =:= Pivot ]
    ++
    sort(Pivot+1, Max, [ X || X <- List, X > Pivot ]).

ちなみにErlangにはlists:sort/1というライブラリ関数がある。
で、テスト用のコードのほうがErlangらしいかも

 -module(testsort).
 -compile(export_all).

doit(0) -> io:format("test done~n",);
doit(N) ->
  Size = random:uniform(N),
  {Min, Max, List} = makelist(N,, N),
  io:format("Min ~p, Max ~p, Size ~p List ~p~n", [Min, Max, Size, List]),
  BIFresult = lists:sort(List),
  Myresult = sort:main(Min, Max, Size, List),
  if
        BIFresult =:= Myresult -> io:format("OK ~p~n",[Myresult]),
        doit(N - 1);
        true -> io:format("Error: ~p : ~p~n", [BIFresult, Myresult])
  end.

makelist(0, L, _N) -> {lists:min(L), lists:max(L),lists:reverse(L)};
makelist(Size, L, N) -> makelist(Size - 1, [random:uniform(N) - (N div 2) | L], N).

こんな風に使う

16> testsort:doit(19).
Min -8, Max 10, Size 6 List [-2,-5,-5,-3,-8,-7,4,-4,3,3,10,4,8,-5,-5,10,-3,10,9]
OK [-8,-7,-5,-5,-5,-5,-4,-3,-3,-2,3,3,4,4,8,9,10,10,10]
Min -8, Max 8, Size 4 List [-8,4,-4,6,6,-3,1,8,-6,4,-2,3,8,3,4,-8,-7,-2]
OK [-8,-8,-7,-6,-4,-3,-2,-2,1,3,3,4,4,4,6,6,8,8]
Min -7, Max 8, Size 5 List [6,-7,-4,-1,-7,8,-7,-1,3,7,4,-5,0,6,1,-6,0]
OK [-7,-7,-7,-6,-5,-4,-1,-1,0,0,1,3,4,6,6,7,8]
Min -7, Max 8, Size 1 List [1,-5,6,-7,-4,-4,-5,8,2,3,-3,2,-1,2,-3,4]
OK [-7,-5,-5,-4,-4,-3,-3,-1,1,2,2,2,3,4,6,8]
Min -6, Max 7, Size 1 List [1,-4,5,4,3,2,1,2,-3,-6,1,0,7,4,5]
OK [-6,-4,-3,0,1,1,1,2,2,3,4,4,5,5,7]
Min -6, Max 7, Size 4 List [4,7,2,-4,7,-6,2,7,1,2,-3,-6,5,-6]
OK [-6,-6,-6,-4,-3,1,2,2,2,4,5,7,7,7]
Min -4, Max 7, Size 6 List [5,2,5,6,7,-4,1,-1,-2,5,0,-1,0]
OK [-4,-2,-1,-1,0,0,1,2,5,5,5,6,7]
Min -5, Max 4, Size 5 List [3,2,-5,-5,3,-2,-2,4,-5,1,-3,-2]
OK [-5,-5,-5,-3,-2,-2,-2,1,2,3,3,4]
Min -2, Max 6, Size 7 List [2,2,6,3,-1,0,1,-2,6,1,3]
OK [-2,-1,0,1,1,2,2,3,3,6,6]
Min -4, Max 5, Size 6 List [1,4,3,0,-3,0,5,-3,0,-4]
OK [-4,-3,-3,0,0,0,1,3,4,5]
Min -2, Max 5, Size 9 List [3,1,-1,-2,5,-1,2,-1,4]
OK [-2,-1,-1,-1,1,2,3,4,5]
Min -2, Max 4, Size 8 List [4,-2,1,3,2,-1,1,2]
OK [-2,-1,1,1,2,2,3,4]
Min -1, Max 3, Size 1 List [-1,0,2,-1,0,0,3]
OK [-1,-1,0,0,0,2,3]
Min -2, Max 2, Size 6 List [-2,-2,2,0,0,-1]
OK [-2,-2,-1,0,0,2]
Min -1, Max 3, Size 1 List [2,1,2,-1,3]
OK [-1,1,2,2,3]
Min -1, Max 2, Size 4 List [2,0,-1,-1]
OK [-1,-1,0,2]
Min 0, Max 0, Size 1 List [0,0,0]
OK [0,0,0]
Min 1, Max 1, Size 2 List [1,1]
OK [1,1]
Min 1, Max 1, Size 1 List [1]
OK [1]
test done
ok