# To make comments in the programs, use the symbol #. Maple
# will ignore everything after the #

# To make a procedure called SortList, start
# with SortList := proc(arg1, arg2, ...) where arg1, arg2, ...
# are the inputs of the procedure.
# Then write a sequence of commands, and end each command
# with a colon or semi-colon.
#
# The output of the procedure is the last thing that gets
# computed. Or you can use:   return output
# to end the computation and return the output.

SortList:=proc(L)         # SortList takes only 1 argument L

	local L1,L2,n,half; # Use these local variables. A local variable
                            # is a variable that only exists inside this
                            # procedure. Suppose that a user had his/her
                            # own variable n, then this local n will be
                            # a different variable.

	options trace;    # Use options trace until you found all the
                          # bugs. The options trace will cause this
                          # procedure to print what it is doing.
                          # When all errors are found and the procedure
                          # works then remove this line, or put a #
                          # in front of it so Maple will ignore it.

	n := nops(L);     # Number of elements of the list.

	if n <= 1 then    # If n = 0 or 1 then we're done.
		return L;
	fi;               # "fi" is a reversed "if". It is used to end
                          # the if command. The if..then..else..fi;
                          # is considered a command, so you end it with
                          # a colon or semi-colon. The return L; is
                          # also one command, you could put a (semi)-colon
                          # behind it, but it's not necessary because
                          # Maple knows the command ends there because the
                          # next thing Maple sees is the "fi".

	# So at this point in the code n must be > 1.

	half := floor(n/2); # floor means round off to below.
	L1 := L[1..half];   # first half of L
	L2 := L[half+1..n]; # second half of L.

	L1 := procname(L1); # Now L1 is sorted.
	L2 := procname(L2); # Now L2 is sorted. Note, the word
                            # procname means something special in Maple,
                            # it refers to the name of the current procedure.
                            # Instead of procname you could also have used
                            # the name of this procedure, which is SortList.

	MergeLists(L1,L2);  # Now MergeLists(L1,L2) is the last thing that's
                            # evaluated, so that will be the output of
                            # SortList in case n is not <= 1.
end;
# After the end you can put either a colon : or a semi-colon ;
# The only difference is that when you put a semi-colon, then
# Maple will display the procedure when you're reading this
# procedure into Maple.



MergeLists := proc(L1, L2)
	local c1, c2, n1, n2, result;
	options trace;

	c1, c2 := 1, 1;     # This is the same as: c1:=1; c2:=1;
                            # It is a multiple assignment. Here it doesn't
                            # make much difference if I use one multiple
                            # or two single assignments, but sometimes it's
                            # handy, e.g. if you want to interchange variables
                            # a and b you just do: a,b := b,a;

	n1, n2 := nops(L1), nops(L2);
	result := NULL;     # Maple has sequences. A sequence is just things
                            # seperated by commas, e.g.  S := 3, 5, 2, 7;
                            # NULL is the empty sequences, so if you do
                            # say S := NULL, S;    then S won't change.

	while c1 <= n1 or c2 <= n2 do    # keep on repeating until the
                                   # boolean expression "c1<=n1 or c2<=n2"
                                   # becomes false
		if c1 > n1 or ( c2<=n2 and L2[c2]<L1[c1] ) then
			result := result, L2[c2] ;  # Add L2[c2] to the result.
			c2 := c2+1
		else
			result:=result, L1[c1] ;
			c1 := c1+1
		fi
	od;
	[ result ];         # a sequence 2, 5, 3, 9 becomes a list
                            # [2, 5, 3, 9] by putting brackets around.
                            # This is the last evaluated expression, so
                            # it's the output of this procedure.
end;






# Now in short, without the options trace and all the
# comments, and I'm combining some commands in just one line,
# you get the following:

SortList:=proc(L)
	local half,n;
	n := nops(L);
	if n<=1 then
		return L
	fi;
	half := floor(n/2);
	MergeLists(procname(L[1..half]), procname(L[half+1..n]))
end:

MergeLists := proc(L1, L2)
	local c1, c2, n1, n2, result;
	c1, c2 := 1, 1;
	n1, n2 := nops(L1), nops(L2);
	result := NULL;
	while c1 <= n1 or c2 <= n2 do
		if c1 > n1 or ( c2<=n2 and L2[c2]<L1[c1] ) then
			result := result,L2[c2];
			c2 := c2+1
		else
			result := result,L1[c1];
			c1 := c1+1
		fi
	od;
	[result]
end:

# Try it out:
# L := [4,5,2,20,4,5,1,3,12,100,-50,2];
# L := SortList(L);
# result:   [-50, 1, 2, 2, 3, 4, 4, 5, 5, 12, 20, 100]
# so it works.


# Here is another way to write the merging algorithm:

MergeLists := proc(L1, L2)
        local c1, c2, n1, n2, k, r;
        c1, c2 := 1, 1;
        n1, n2 := nops(L1), nops(L2);
        for k to n1+n2 do
                if c1 > n1 or ( c2<=n2 and L2[c2]<L1[c1] ) then
                        r[k] := L2[c2];
                        c2 := c2+1
                else
                        r[k] := L1[c1];
                        c1 := c1+1
                fi
        od;
        [seq(r[k], k=1..n1+n2)]
end:


# Try a bigger example:
# L:=[seq(rand(-10000..10000)(),i=1..1000)];
# Explanation: rand(-10000..10000)() is a random number in the
# range -10000..10000.
# The command seq(expression, i=1..1000) makes a sequence, namely:
# expression evaluated with i=1, expression evaluated with i=2, ...
# The brackets [ ] make the sequence into a list.
# Now sort:  SortList(L);
# Note that Maple already has a sorting command built in:  sort