(New page: Category:ECE608Spring2009ghafoor ==Description== Merge sort is a divide and conquer algorithm that orders a list of elements. ==Performance== <table class="wikitable" style="bord...) |
m |
||
Line 57: | Line 57: | ||
(if (or (= (length l) 1) (= (length l) 0)) | (if (or (= (length l) 1) (= (length l) 0)) | ||
l | l | ||
− | (merge-sort-merge (merge-sort (first-n-items (get-q 1 l) l)) (merge-sort (after-n-items (get-q 1 l) l))))) | + | (merge-sort-merge |
+ | (merge-sort (first-n-items (get-q 1 l) l)) | ||
+ | (merge-sort (after-n-items (get-q 1 l) l))))) | ||
</source> | </source> | ||
[[Category:ECE608]] | [[Category:ECE608]] | ||
[[Category:Sorting algorithms]] | [[Category:Sorting algorithms]] |
Latest revision as of 13:05, 14 January 2009
Description
Merge sort is a divide and conquer algorithm that orders a list of elements.
Performance
Best | Average | Worst |
---|---|---|
$ O(nlog_2(n)) $ | $ O(nlog_2(n)) $ | $ O(nlog_2(n)) $ |
Example
LISP implementation
;Stephen Rudolph ;1/14/09 ;Merge-Sort ;;Return a list containing the first n items in the list l (defun first-n-items(n l) (if (= n 1) (list (car l)) (cons (car l) (first-n-items (- n 1) (cdr l))))) ;;Return a list containing all elements after the nth element (defun after-n-items(n l) (if (= n 0) l (after-n-items (- n 1) (cdr l)))) ;;Get the q value for the merge-sort function (defun get-q(p l) (floor (/ (+ p (length l)) 2))) ;;Merge two sorted lists (defun merge-sort-merge(l1 l2) (if (= (length l2) 0) l1 (if (= (length l1) 0) l2 (if (<= (car l1) (car l2)) (cons (car l1) (merge-sort-merge (cdr l1) l2)) (cons (car l2) (merge-sort-merge l1 (cdr l2))))))) ;;Sort list l with the insertion sort algorithm (defun merge-sort(l) (if (or (= (length l) 1) (= (length l) 0)) l (merge-sort-merge (merge-sort (first-n-items (get-q 1 l) l)) (merge-sort (after-n-items (get-q 1 l) l)))))