(defun my-merge-sort--split (xs)
  "Return a list with the two halves of XS."
  (let ((length (length xs)))
    (pcase length
      (0 (list nil nil))
      (1 (list xs nil))
      (_ (let ((half (/ length 2)))
           (list (take half xs)
                 (drop half xs)))))))

(ert-deftest my-merge-sort--split ()
  (should (equal (my-merge-sort--split '()) '(() ())))
  (should (equal (my-merge-sort--split '(1)) '((1) ())))
  (should (equal (my-merge-sort--split '(1 2)) '((1) (2))))
  (should (equal (my-merge-sort--split '(1 2 3)) '((1) (2 3))))
  (should (equal (my-merge-sort--split '(1 2 3 4)) '((1 2) (3 4)))))



(defun my-merge-sort--merge (lhs rhs)
  "Return a sorted list by merging sorted lists LHS and RHS."
  (cond
   ((null lhs) rhs)
   ((null rhs) lhs)
   ((<= (car lhs) (car rhs))
    (cons (car lhs) (my-merge (cdr lhs) rhs)))
   ((> (car lhs) (car rhs))
    (cons (car rhs) (my-merge (cdr rhs) lhs)))))



(defun my-merge-sort (xs)
  "Return XS sorted by Merge Sort."
  (if (< (seq-length xs) 2) xs
    (let ((halves (my-merge-sort--split xs)))
      (my-merge-sort--merge (my-merge-sort (nth 0 halves))
                            (my-merge-sort (nth 1 halves))))))

(ert-deftest my-merge-sort ()
  (should (equal (my-merge-sort '()) '()))
  (should (equal (my-merge-sort '(1)) '(1)))
  (should (equal (my-merge-sort '(1 2)) '(1 2)))
  (should (equal (my-merge-sort '(2 1)) '(1 2)))
  (should (equal (my-merge-sort '(1 2 3)) '(1 2 3)))
  (should (equal (my-merge-sort '(1 3 2)) '(1 2 3)))
  (should (equal (my-merge-sort '(2 1 3)) '(1 2 3)))
  (should (equal (my-merge-sort '(2 3 1)) '(1 2 3)))
  (should (equal (my-merge-sort '(3 1 2)) '(1 2 3)))
  (should (equal (my-merge-sort '(3 2 1)) '(1 2 3)))
  (should (equal (my-merge-sort '(1 2 3 4)) '(1 2 3 4)))
  (should (equal (my-merge-sort '(4 3 2 1)) '(1 2 3 4))))