Download code

Jump to: navigation, search

Back to Merge_sort_(Erlang)

Download for Windows: single file, zip

Download for UNIX: single file, zip, tar.gz, tar.bz2

mergesort.erl

 1 % The authors of this work have released all rights to it and placed it
 2 % in the public domain under the Creative Commons CC0 1.0 waiver
 3 % (http://creativecommons.org/publicdomain/zero/1.0/).
 4 % 
 5 % THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 6 % EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 7 % MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 8 % IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 9 % CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
10 % TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
11 % SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
12 % 
13 % Retrieved from: http://en.literateprograms.org/Merge_sort_(Erlang)?oldid=8158
14 
15 -module(mergesort).
16 -export(msort/2, msort_lte/1, msort_gte/1).
17 
18 split(Ls) ->
19     split(Ls, Ls, []).
20 
21 split([], Ls1, Ls2) ->
22     {reverse(Ls2) , Ls1};
23 
24 split([_], Ls1, Ls2) ->
25     {reverse(Ls2) , Ls1};
26 
27 split([_,_|TT], [Ls1_H | Ls1_T], Ls2) ->
28     split(TT, Ls1_T, [Ls1_H | Ls2]).
29 
30 
31 
32 merge(_, [], Ls2) ->
33     Ls2;
34 merge(_, Ls1, []) ->
35     Ls1;
36 merge(Rel, [H1|T1], [H2|T2]) ->
37     case Rel(H1, H2) of
38 	true ->
39 	    [H1 | merge(Rel, T1, [H2|T2])];
40 	false ->
41 	    [H2 | merge(Rel, [H1|T1], T2)]
42     end.
43 
44 msort(_, []) ->
45     [];
46 msort(_, [H]) ->
47     [H];
48 msort(Rel, Ls) ->
49     {Half1 , Half2} = split(Ls),
50     merge(Rel, msort(Rel, Half1), msort(Rel, Half2)).
51 
52 % Parameterize msort with commonly-used predicates
53 lte(X, Y) ->
54     (X < Y) or (X == Y).
55 
56 gte(X, Y) ->
57     (X > Y) or (X == Y).
58 
59 msort_lte(Ls) ->
60     msort(fun lte/2, Ls).
61 
62 msort_gte(Ls) ->
63     msort(fun gte/2,
64 	  Ls).
65 


hijacker
hijacker
hijacker
hijacker