Non-destructive sort in lisp?

Question

I have been tasked to create a program, and within it I require a function to return a sorted list (in alphabetical order). However, I am unable to use and "non-functional" functions eg "set, setq" etc... And that includes the built in sort function (because it is destructive). So, I was wondering if there is a way to build a non-destructive sort in lisp?

Answer 1

The easiest way would be to make a copy before sorting:

(sort (copy-seq input) predicate)

Or you write a sort function yourself, e.g. quicksort:

(defun qsort (input predicate)
  (if input
    (let* ((pivot (first input))
           (rest (rest input))
           (lesser (remove-if-not #'(lambda (x)
                                      (funcall predicate x pivot))
                                  rest))
           (greater (remove-if-not #'(lambda (x)
                                       (not (funcall predicate x pivot)))
                                   rest)))
      (append (qsort lesser predicate)
              (list pivot)
              (qsort greater predicate)))
    nil))

(Demo)

Note that one could optimize this to detect already sorted rests of a list, enabling structure sharing between the unsorted and sorted list.