CODEWITHSUNDEEP
lispcommon-lisp
HeartbeatDeveloper
HeartbeatDeveloper

Reputation: 43

Difficulty writing LISP Recursive Function for Merge Sort

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))

           )))
  )

Upvotes: 4

Views: 2201

Answers (1)

Barmar
Barmar

Reputation: 780798

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)))))

Upvotes: 7

Related Questions