Scheme infinite recursion

Question

I'm writing my own version of quicksort, and something is causing an infinite recursion that I can't track down for some reason.

(define (quicksort-test list)
  (cond
    ((null? list) '())
    (else
     (appending (quicksort-test (less-than-builder list (car list)))
                (quicksort-test (geq-builder list (car list)))))))

Appending is a helper function which just appends one list onto another, and less-than-builder and geq-builder are helper functions which take a list and a pivot as inputs, and then build a list of everything less than the pivot and a list of everything greater than or equal to the pivot, respectively. I think the problem is in my else statement, though I can't see why for some reason, maybe due to a fried brain.

Answer 1

Building a list of every element that's greater than or equal to a pivot element will never return an empty list, it will just get down to a single element and keep calling itself over and over again because a list with a single element is always greater than or equal to itself.

You need to remove the pivot element – recurse on (cdr list) – and put it back in the middle afterwards.

Credit goes to molbdnilo and Eddie V for solving this problem in the comments