Contents    Page-10    Prev    Next    Page+10    Index   

Sorting by Merge

A list of length 0 or 1 is already sorted. Otherwise, break the list in half, sort the halves, and merge them.

public static Cons llmergesort (Cons lst) {
  if ( lst == null || rest(lst) == null)
     return lst;
   else { Cons mid = midpoint(lst);
          Cons half = rest(mid);
          setrest(mid, null);
          return dmerj( llmergesort(lst),
                        llmergesort(half)); } }

(defun llmergesort (lst)
  (let (mid half)
    (if (or (null lst) (null (rest lst)))
        (progn (setq mid (midpoint lst))
               (setq half (rest mid))
               (setf (rest mid) nil)
               (dmerj (llmergesort lst)
                      (llmergesort half)) ) )) ))          

What is O()? Stack depth? Conses?