[erlang-questions] Bucket Sort

[Colm Dougan]

On Fri, May 22, 2009 at 1:03 AM, tonakai <aykutsoysal@REDACTED> wrote:
> hi,
> i've implement a concurrent bucket sort in erlang, but its kind of
> slow (slower then the sequential version)
> i think my mistake is that i first create the buckets, then i send
> them to processes i spawned. Will it increase the speed if i send each
> integer to processes rather then sending the list at the end? i am
> thinking that will increase message-passing...

Interesting problem.  I don't know enough about the performance
characteristics of bucket sorting to know whether it would be expected
to out-perform lists:sort.   However, I think the initial grouping by
bucket can be improved by using the 'array' abstraction rather than a
'dict', as follows :

divide2(List, N, Max) ->
    array:sparse_to_orddict(
    lists:foldl(
       fun(El, Acc) ->
           Bucket = ((Max div N)*(El div (Max div N))),
           array:set(Bucket, [El | array:get(Bucket, Acc)], Acc)
       end,
       array:new([{default, []}]),
       List
    )).

The list of lists this produces is sorted by bucket (but the inner
lists are not sorted).

Colm