## Shortest quicksort

8th September 2020

In an earlier post I proposed the challenge of writing the shortest Common Lisp function to sort a list of numbers into ascending order: Shortest sort answers.

I was recently experimenting with applying the same challenge to a quicksort. For example:

```CL-USER > (quicksort '(3 1 4 1 5 9 2 6 5 3 5 8))
(1 1 2 3 3 4 5 5 5 6 8 9)```

The solution can use any Common Lisp functions you want, apart, of course, from sort or stable-sort.

To get the score, count the non-nil atoms in the function definition(s) using count-atoms:

```(defun count-atoms (form)
(typecase form
(null 0)
(atom 1)
(cons (+ (count-atoms (car form))
(count-atoms (cdr form))))))```

### Best solution

Here's the best solution that I've found, with a count of 28 non-nil atoms:

```(defun quicksort (lis)
(when lis
(destructuring-bind (p . r) lis
(flet ((less (x) (< x p)))
(append (quicksort (remove-if-not #'less r))
(list p)
(quicksort (remove-if #'less r)))))))```

It works as follows:

• Choose a 'pivot' element p in the list to be sorted and remove it from the list to give a list r. For simplicity this function chooses the first item in the list as the pivot.
• Split r into two lists: a, containing all the elements less than p, and b, containing all the elements greater than p.
• Recursively call quicksort on a and b.
• The result is got by appending a, (list p), and b.

Can you improve on this solution?