Skip to content

Instantly share code, notes, and snippets.

@isterin
Created February 10, 2011 20:33
Show Gist options
  • Save isterin/821271 to your computer and use it in GitHub Desktop.
Save isterin/821271 to your computer and use it in GitHub Desktop.
Merge sort implementation in lisp
(defun merge-sort (lst)
(let ((size (length lst)))
(if (= size 1)
lst
(progn
(let ((seq1 (merge-sort (subseq lst 0 (floor (/ size 2)))))
(seq2 (merge-sort (subseq lst (floor (/ size 2)) size))))
(merge-it seq1 seq2))))))
(defun merge-it (l1 l2)
(let ((new-arr (make-array (+ (length l1)
(length l2))
:fill-pointer 0)))
(loop for idx from 0 to (+ (length l1) (length l2)) do
(let ((x (car l1))
(y (car l2)))
(when (and (not (null x)) (not (null y)))
(if (<= x y)
(progn
(setf l1 (cdr l1))
(vector-push x new-arr))
(progn
(setf l2 (cdr l2))
(vector-push y new-arr))))))
(mapcar #'(lambda (e) (vector-push e new-arr)) (append l1 l2))
(coerce new-arr 'list)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment