MergeSort

(defun merge-lists (xs ys cmp)
  (labels ((rec (xs ys acc)
         (cond
           ((and (null xs) (null ys))
        acc)
           ((null ys)
        (append (reverse xs) acc))
           ((null xs)
        (rec ys xs acc))
           ((funcall cmp (car ys) (car xs))
        (rec xs (cdr ys) (cons (car ys) acc)))
           (t
        (rec ys (cdr xs) (cons (car xs) acc))))))
    (nreverse (rec xs ys '()))))
(defun split-list (xs)
  (labels ((rec (xs acc)
         (if (null xs)
         acc
         (rec (cdr xs) (cons (list (car xs)) acc)))))
    (rec xs nil)))
(defun merge-lists-by-two (xss cmp)
  (labels ((rec (xss acc)
         (if (cadr xss)
         (rec (cddr xss)
              (cons
               (merge-lists (car xss) (cadr xss) cmp) acc))
         (if (null xss)
             acc
             (cons (car xss) acc)))))
    (rec xss '())))
(defun merge-sort (xs &optional (cmp #'<=))
  (labels ((rec (xss)
       (if (cadr xss)
           (rec (merge-lists-by-two xss cmp))
           xss)))
    (car (rec (split-list xs)))))