Difficulty writing LISP Recursive Function for Merge Sort

Question

Hi so I have question that I am having some difficulty solving see below

Use the function SPLIT-LIST and MERGE-LISTS to define a recursive Lisp function MSORT such that if L is a list of real numbers then (MSORT L) is a list consisting of the elements of L in ascending order. In the definition of MSORT you may call SPLIT-LIST, MSORT itself, MERGE-LISTS, CAR, CDR, CADR and ENDP, but you should not call any other function. Be sure to use LET or LET*, so that MSORT only calls SPLIT-LIST once.

So far I was able to write the SPLIT-LIST and MERGE-LISTS functions correctly but for M-SORT I am having difficulty writing the function. See below all three definitions so far. Any help on how to write the MSORT function correctly by following the guidelines in the question would be appreciated.

(defun SPLIT-LIST (L)
  (if (endp L)
      '(nil nil)
    (let ((X (split-list (cdr L))))
      (list  (cons (car L)(cadr X)) (car X) ))))

(defun MERGE-LISTS (L1 L2)
  (cond
   ((and(endp L1 )(endp L2)) nil )
   ((endp L1) (cons (CAR L2) (MERGE-LISTS nil (CDR L2))))
   ((endp L2) (cons (CAR L1) (MERGE-LISTS (CDR L1) NIL)))
   ((< (CAR L1) (CAR L2)) (cons (CAR L1) (MERGE-LISTS (CDR L1) L2  )))  
   ((>= (CAR L1) (CAR L2)) (cons (CAR L2) (MERGE-LISTS L1 (CDR L2))  ))))

(defun MSORT (L)
  (cond ((endp L ) nil)
        ( (equal (Length L) 1) L)
        (T
         (let* (
                (S (SPLIT-LIST L ))
                (L1 (CAR S))
                (L2 (CADR S))
                (X (MSORT (cdr L1)))
                (Y (MSORT (cdr L2)))


                )
           (MERGE-LISTS 
            (if (and (numberp (car L1)) (numberp (car X))(<=  (car L1 ) (car X)))  
                (list (car L1) (car X))
              (list (car X) (car L1) )
              ) 

            (Cons (car L2) Y))

           )))
  )

Why are you calling MSORT only on the cdr of L1 and L2? Sort each of them entirely and then merge the results. — Barmar
– Barmar, Commented Mar 24, 2016 at 4:50
I assume that the point here is to implement these yourself, but do note that Common Lisp provides a merge function that works with lists (and vectors!). (Of course, it also provides a sort function, but that isn't necessarily a merge sort.) — Joshua Taylor
– Joshua Taylor, Commented Mar 24, 2016 at 12:36

Barmar · Accepted Answer · 2016-03-24 04:55:17Z

7

You're overcomplicating it. You don't need to sort the CDRs of the sub-lists returned by SPLIT-LIST, just sort the whole lists, and merge them.

(defun MSORT (L)
  (cond ((endp L) nil)
        ((endp (cdr L)) L)
        (t
         (let* ((S (SPLIT-LIST L ))
                (L1 (car S))
                (L2 (cadr S))
                (X (MSORT L1))
                (Y (MSORT L2)))
           (MERGE-LISTS X Y)))))

answered Mar 24, 2016 at 4:55

Barmar

789k57 gold badges555 silver badges669 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

HeartbeatDeveloper Over a year ago

Thank you so much Barmar. You are a life saver. Yes the point was to write this function myself. I don't know why I was over complicating it. It makes perfect sense what you gave.

Collectives™ on Stack Overflow

Difficulty writing LISP Recursive Function for Merge Sort

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related