Skip to content

Instantly share code, notes, and snippets.

@sdebnath
Created March 15, 2015 22:41
Show Gist options
  • Save sdebnath/a0cfed12cab3a0e2d761 to your computer and use it in GitHub Desktop.
Save sdebnath/a0cfed12cab3a0e2d761 to your computer and use it in GitHub Desktop.
Mergesort in Erlang
%%==============================================================================
%% Mergesort implementation in Erlang
%%
%% Author: Shawn Debnath
%%==============================================================================
%%----------------------------------------------------------------------
%% msort/1
%%
%% Mergesort (recursive), implements split and merge.
%%----------------------------------------------------------------------
msort([]) -> [];
msort([H]) ->
[H];
msort(List) ->
{Front, Back} = split(List),
merge(msort(Front), msort(Back)).
split(List) ->
split(List, List, []).
split([], Back, Front) ->
{lists:reverse(Front), Back};
split([_], Back, Front) ->
{lists:reverse(Front), Back};
split([_,_ | Counter], [H | T], Result) ->
split(Counter, T, [H | Result]).
merge([], Back) ->
Back;
merge(Front, []) ->
Front;
merge([L | Front], [R | Back]) when L < R ->
[L | merge(Front, [R | Back])];
merge([L | Front], [R | Back]) ->
[R | merge([L | Front], Back)].
@dev-chip
Copy link

The lists:reverse() function is not required.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment