Created
August 17, 2008 06:50
-
-
Save jchris/5794 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
-module(mergesort). | |
-export([sort/1]). | |
% Usage: | |
% c(mergesort). | |
% | |
% mergesort:sort([2,7,55,4,30,6,7,99,1,100]). | |
% => [1,2,4,6,7,7,30,55,99,100] | |
sort([]) -> []; | |
sort([L]) -> [L]; | |
sort(List) -> | |
Middle = length(List) div 2, | |
{Left, Right} = lists:split(Middle, List), | |
merge(sort(Left),sort(Right)). | |
merge(Left, Right) -> merge(Left, Right, []). | |
merge([L|Left], [R|Right], Acc) when L < R -> | |
merge(Left, [R|Right], [L|Acc]); | |
merge(Left, [R|Right], Acc) -> | |
merge(Left, Right, [R|Acc]); | |
merge([L|Left], [], Acc) -> | |
merge(Left, [], [L|Acc]); | |
merge([], [R|Right], Acc) -> | |
merge([], Right, [R|Acc]); | |
merge([], [], Acc) -> lists:reverse(Acc). | |
% From a comment by Per Gustafsson | |
% http://jchris.mfdz.com/life/2008/8/erlang_mergesort#comments | |
% In this case I think it is actually better to not use a tail | |
% recursive definition of merge. I am pretty sure that this is | |
% more efficient: | |
% (Note from jchris) I'm not sure what impact this will have | |
% on memory requirements. | |
merge(Left, []) -> Left; | |
merge([], Right) -> Right; | |
merge([L|Left], [R|_] = Right) when L < R -> | |
[L | merge(Left, Right)]; | |
merge(Left, [R|Right], Acc) -> | |
[R | merge(Left, Right)]. | |
% If you still want a tail recursive version it should probably | |
% look something like this: | |
merge(Left, [], Acc) -> lists:reverse(Acc, Left); | |
merge([], Right, Acc) -> lists:reverse(Acc, Right); | |
merge([L|Left], [R|_] = Right) when L < R -> | |
merge(Left, Right, [L|Acc]); | |
merge(Left, [R|Right], Acc) -> | |
merge(Left, Right, [R|Acc]). | |
% lists:reverse(List, Tail) is equivalent to | |
% lists:reverse(List) ++ Tail but is more efficient. | |
% The Wikipedia version | |
% from http://en.wikipedia.org/wiki/Merge_sort | |
% function mergesort(m) | |
% var list left, right, result | |
% if length(m) ≤ 1 | |
% return m | |
% | |
% var middle = length(m) / 2 | |
% for each x in m up to middle | |
% add x to left | |
% for each x in m after middle | |
% add x to right | |
% left = mergesort(left) | |
% right = mergesort(right) | |
% result = merge(left, right) | |
% return result | |
% | |
% function merge(left,right) | |
% var list result | |
% while length(left) > 0 and length(right) > 0 | |
% if first(left) ≤ first(right) | |
% append first(left) to result | |
% left = rest(left) | |
% else | |
% append first(right) to result | |
% right = rest(right) | |
% end while | |
% if length(left) > 0 | |
% append rest(left) to result | |
% if length(right) > 0 | |
% append rest(right) to result | |
% return result | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment