Commits

orbitz  committed 826e69c

Adding merge sort

  • Participants

Comments (0)

Files changed (1)

File sorting/merge_sort.erl

+%%%-------------------------------------------------------------------
+%%% @author orbitz <orbitz@gmail.com>
+%%% @copyright (C) 2011, orbitz
+%%% @doc
+%%%
+%%% @end
+%%% Created : 17 Oct 2011 by orbitz <orbitz@gmail.com>
+%%%-------------------------------------------------------------------
+-module(merge_sort).
+
+%% API
+-export([sort/1, sort/2]).
+
+%%%===================================================================
+%%% API
+%%%===================================================================
+
+%%--------------------------------------------------------------------
+%% @doc
+%% Sort a list in ascending order
+%% @spec
+%% @end
+%%--------------------------------------------------------------------
+sort(List) ->
+    sort(List, fun default_compare/2).
+
+
+%%--------------------------------------------------------------------
+%% @doc
+%% Sort a list with a a custom compare function
+%% @spec
+%% @end
+%%--------------------------------------------------------------------
+sort([], _Compare) ->
+    [];
+sort([X], _Compare) ->
+    [X];
+sort(List, Compare) ->
+    {L1, L2} = split_list(List),
+    merge_lists(sort(L1, Compare), sort(L2, Compare), Compare).
+
+%%%===================================================================
+%%% Internal functions
+%%%===================================================================
+default_compare(E1, E2) when E1 < E2 ->
+    less_than;
+default_compare(E1, E2) when E1 > E2 ->
+    greater_than;
+default_compare(_, _) ->
+    equal.
+
+
+split_list(List) ->
+    split_list(List, [], []).
+
+split_list([], L1, L2) ->
+    {L1, L2};
+split_list([X], L1, L2) ->
+    {[X | L1], L2};
+split_list([X | [Y | Rest]], L1, L2) ->
+    split_list(Rest, [X | L1], [Y | L2]).
+    
+merge_lists([], [], _Compare) ->
+    [];
+merge_lists(List, [], _Compare) ->
+    List;
+merge_lists([], List, _Compare) ->
+    List;
+merge_lists([L | LRest] = Left, [R | RRest] = Right, Compare) ->
+    case Compare(L, R) of
+        less_than ->
+            [L | merge_lists(LRest, Right, Compare)];
+        equal ->
+            [L | [R | merge_lists(LRest, RRest, Compare)]];
+        greater_than ->
+            [R | merge_lists(Left, RRest, Compare)]
+    end.