Merge Sort                            CSE 215 Fall 2007


In class we defined a function for merge sort that uses 
take and skip functions to split a list into two parts
consisting of elements at even-numbered and odd-numbered
positions, respectively. It is more common, though, to
split a list at the midpoint into a first and second half;
see also the example given in class. The following
functions can be used for that purpose.

    firstk(L, k) returns the list of the first k 
                 elements of L.

    dropk(L, k)  returns the list of all but the 
                 first k elements of L.

If we take k = length(L) div 2, then we obtain the left and
and right halves of L. Here are SML definitions.

fun firstk(L, k) = 
    if k = 0 then []
    else if L = nil then nil
    else hd(L)::firstk(tl(L), k-1);

fun dropk(L, k) = 
    if k = 0 then L
    else if L = nil then nil
    else dropk(tl(L), k-1);
 
  
fun merge([], M) = M
 |  merge (L, []) = L
 |  merge(x::xl, y::yl) = 
       if (x:int) < y then x::merge(xl, y::yl)
       else y::merge(x::xl, yl);

fun newsort(L) = 
    if L = nil then nil
    else if tl(L) = nil then L
    else merge(newsort(firstk(L,length(L) div 2)),
               newsort(dropk(L, length(L) div 2)));


Try these examples:

val L1 = [3, 4, 2, 1];

val Left = firstk(L1, 2);

val Right = dropk(L1, 2);

val Left_s = newsort(Left);
 
val Right_s = newsort(Right);

merge (Left_s, Right_s);

newsort(L1);