Created
February 10, 2011 20:33
-
-
Save isterin/821271 to your computer and use it in GitHub Desktop.
Merge sort implementation in lisp
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(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