Common Lisp merge sort breaking down

Question

I've challenged myself to do all assignments in my algorithms class in Common Lisp. I'm into day one of learning lisp and I've hit an obstacle.

The assignment is to create a merge sort that converts to insertion when you get to an arbitrary subset length (Timsort). The insertion section works perfectly, but the split part of the merge only works when the program has to split twice. I know it has to do with the way lists work in lisp, I'm just too new to pinpoint the problem.

I think it either hits an infinite loop... I'm not sure because when I run it with debug statements, they never get printed when the set has too many elements.

I'm not here begging for specific answers or for someone to write my code. Maybe an explanation or a point in the right direction would help a lot!

My code:

;; Insertion sort method call (returns sorted list)
(defun insert-sort (lst) ... )

;; Merge sort method call
(defun merge-sort (lst)
  (print 'Merge)
  (print lst)
  (if (< (length lst) 7) ; Check to see if list is small enough to insert sort
      (insert-sort lst) ; Do so
      (progn ; else
        (setf b (merge-split lst)) ; Split the list, store into b
        (setf (car b) (merge-sort (car b))) ; Merge sort on first half
        ;; --- I think it's happening here ---
        (setf (cdr b) (merge-sort (cdr b))) ; Merge sort on second half
        (merge 'list (car b) (cdr b) #'<)))) ; Merge the two lists together (using API)

;; Split a list into two parts
(defun merge-split (lst)
   (progn
     (setf b lst) ; Set b to first index
     (setf a (cdr lst)) ; Set a to the rest of the list
     (loop while a do ; Loop while a != null
           (setf a (cdr a)) ; Make a equal next list node
           (if a ; If it still exists
               (progn
                 (setf a (cdr a)) ; Inc a again
                 (setf b (cdr b))))) ; Also inc b (b should always be half of a)
     (setf a (cdr b)) ; Set a to the list after b
     (setf (cdr b) NIL) ; Delete link after b
     (cons lst a))) ; Return in a cons

Note: This is code I've written, not gotten off the internet... you can probably tell though haha

Answer 1

You're being bitten by dynamically scoped variables. The first time you call SETF to set a, b you implicitly create global, dynamically scoped variables. Use LET instead to declare them. LET allows you to include a list of expressions to execute, just like PROGN, so my hint is that you can fix this by changing your 2 PROGNs into LETs. Let me know if you need more than this to get unstuck.