Hi,
The wikipedia entry on merge sort gives the following lisp
implementation:
(defun merge-sort (list)
(if (endp (rest list)) list
(insert (first list) (merge-sort (rest list)))))
(defun insert (item list)
(if (or (endp list) (< item (car list))) (cons item list)
(cons (first list) (insert item (rest list)))))
Do you think it is the right implementation? I think it is more of a
insertion sort, where time complexity is O(n^2) rather than merge
sort's O(n . log n).
-Vaibhav Kulkarni
On Sep 1, 9:47 pm, ··········@gmail.com wrote:
> The wikipedia entry on merge sort gives the following lisp
> implementation:
I started to replace it with a correct one, but then I read the
discussion page, according to which it was decided some time ago not
to include actual code on algorithm pages, because everyone wants
their favorite language to be represented. So, I simply deleted the
Lisp code.
Yes, there is a C++ implementation there which was added in May.
Since I'm a newcomer to the page, though, I didn't feel right deleting
that; I left it for those who participated in the earlier decision (or
anyone else who feels so inclined, I suppose).
-- Scott
Here's my implementation :
(defun xmerge (l1 l2) (cond ((null l1) l2)
((null l2) l1)
((< (car l1) (car l2) )
(cons (car l1) (xmerge (cdr l1) l2) ))
(T (cons (car l2) (xmerge l1 (cdr
l2)) )) ))
(defun mergesort (lis)(let ((x (list-length lis)))
(if (= x 1) lis
(xmerge (mergesort
(subseq lis 0 (truncate (/ x 2) ) ))
(mergesort (subseq lis (truncate (/ x 2) ) )) )
)))
It could be made shorter / more efficient , with let and a tail-
recursive merge ,
but I ' we written in a hurry , and it gets the idea of mergesort
············@gmail.com writes:
> Here's my implementation :
>
> (defun xmerge (l1 l2) (cond ((null l1) l2)
> ((null l2) l1)
> ((< (car l1) (car l2) )
> (cons (car l1) (xmerge (cdr l1) l2) ))
> (T (cons (car l2) (xmerge l1 (cdr
> l2)) )) ))
>
>
> (defun mergesort (lis)(let ((x (list-length lis)))
> (if (= x 1) lis
> (xmerge (mergesort
> (subseq lis 0 (truncate (/ x 2) ) ))
> (mergesort (subseq lis (truncate (/ x 2) ) )) )
> )))
>
> It could be made shorter / more efficient , with let and a tail-
> recursive merge ,but I ' we written in a hurry , and it gets the idea of mergesort
There is a simpler implementation, using the built-in sequence MERGE
function, but that would perhaps not be as instructive as having the
merge function itself be part of the displayed algorithm:
(defun mergesort (list)
(let* ((len (length list))
(pivot (floor len 2)))
(if (< len 1)
list
(merge 'list
(mergesort (subseq list 0 pivot))
(mergesort (subseq list pivot))
#'<))))
The subsequence solution has the advantage that it would work with any
sequences, and this could perhaps be made more generic by replacing the
constant 'list with (type-of list) instead.
--
Thomas A. Russ, USC/Information Sciences Institute