From: r_stiltskin
Subject: critique my sort please
Date: 
Message-ID: <b6e4df030507821ffcdbbecdb3b08b8c@localhost.talkaboutprogramming.com>
Trying again to find the time to teach myself lisp.   I wrote this
mergesort.  It seems to work, but I'm worrying that all those calls to
"length" are wasteful.  Is there a more efficient way to do this?

(defun msort (ls)
  (cond ((null ls) nil)
	((null (cdr ls)) ls)
	((equal (length ls) 2) (srt ls))
        (t (mrg (msort (front ls)) (msort (back ls)))))) 

(defun front (ls)
  (cond ((null ls) nil)
	(t (front2 ls (ceiling (length ls) 2)))))

(defun front2 (ls len)
  (cond ((equal len 1) (list (car ls)))
	(t (cons (car ls) (front2 (cdr ls) (- len 1))))))

(defun back (ls)
  (cond ((null ls) nil)
	(t (back2 ls (ceiling (length ls) 2)))))

(defun back2 (ls len)
  (cond ((equal len 0) ls)
	(t (back2 (cdr ls) (- len 1)))))

(defun srt (ls)
  (cond ((< (car ls) (car (cdr ls))) ls)
	(t (cons (car (cdr ls)) (list (car ls))))))

(defun mrg (xs ys)
  (cond ((null xs) ys)
	((null ys) xs)
	((< (car xs) (car ys)) (cons (car xs) (mrg (cdr xs) ys)))
	(t (cons (car ys) (mrg xs (cdr ys))))))
 

From: Pascal Bourguignon
Subject: Re: critique my sort please
Date: 
Message-ID: <87ver92mri.fsf@thalassa.informatimago.com>
"r_stiltskin" <········@very.spam.yahoo.com> writes:
> Trying again to find the time to teach myself lisp.   I wrote this
> mergesort.  It seems to work, but I'm worrying that all those calls to
> "length" are wasteful.  Is there a more efficient way to do this?

Probably.

You could pass the length as you do it with front2.


> (defun msort (ls)
>   (cond ((null ls) nil)
> 	((null (cdr ls)) ls)
> 	((equal (length ls) 2) (srt ls))
>         (t (mrg (msort (front ls)) (msort (back ls)))))) 
>
> (defun front (ls)
>   (cond ((null ls) nil)
> 	(t (front2 ls (ceiling (length ls) 2)))))
>
> (defun front2 (ls len)
>   (cond ((equal len 1) (list (car ls)))
> 	(t (cons (car ls) (front2 (cdr ls) (- len 1))))))
>
> (defun back (ls)
>   (cond ((null ls) nil)
> 	(t (back2 ls (ceiling (length ls) 2)))))
>
> (defun back2 (ls len)
>   (cond ((equal len 0) ls)
> 	(t (back2 (cdr ls) (- len 1)))))
>
> (defun srt (ls)
>   (cond ((< (car ls) (car (cdr ls))) ls)
> 	(t (cons (car (cdr ls)) (list (car ls))))))
>
> (defun mrg (xs ys)
>   (cond ((null xs) ys)
> 	((null ys) xs)
> 	((< (car xs) (car ys)) (cons (car xs) (mrg (cdr xs) ys)))
> 	(t (cons (car ys) (mrg xs (cdr ys))))))



Also, you can define front and back as you want. 
So you could split the list "longitudinally", collecting the elements
at odd  positions in the back list and those at even positions in the
front list:

(defun split (list front back)
  (cond
    ((null list)       (cons front back))
    ((null (cdr list)) (cons (cons (car list) front) back))
    (t (split (cddr list)
              (cons (car list) front)
              (cons (cadr list) back)))))

Then you wouldn't have to compute the lengths at all:

(defun msort (list)
  (cond ((null list)       list)
        ((null (cdr list)) list)
        (t (let ((split (split list '() '())))
              (mrg (msort (car split)) (msort (cdr split)))))))


-- 
__Pascal Bourguignon__                     http://www.informatimago.com/

PLEASE NOTE: Some quantum physics theories suggest that when the
consumer is not directly observing this product, it may cease to
exist or will exist only in a vague and undetermined state.
From: r_stiltskin
Subject: Re: critique my sort please
Date: 
Message-ID: <a167b766bbcda70c5bd7a6b8520db9ff@localhost.talkaboutprogramming.com>
Thank you, Pascal.  Besides being more efficient, yours is quite a bit more
elegant as well. I like that "two lists in one" approach.  :)