## Shortest sort answers

24th April 2018

A week ago I presented a challenge of finding the shortest Common Lisp function to sort a list of numbers into ascending order, without using **sort** or **stable-sort**.

The size was to be evaluated by counting 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))))))

Here's a summary of the contributed answers :

### Selection sort (20)

When I presented the challenge the answer I had in mind was:

(defun mysort (lst) (if (null lst) nil (let ((min (apply #'min lst))) (cons min (mysort (remove min lst :count 1))))))

which has a score of 20. This recursively extracts the smallest number and puts it at the beginning of the sorted list of the remaining items.

**Rainer Joswig** pointed out on Twitter that **apply** should be replaced with **reduce**, because **apply** is limited to the number of arguments specified by **CALL-ARGUMENTS-LIMIT**.

### Version using loop (23)

For those who like **loop**, **alandipert** suggested the following similar solution:

(defun mysort (xs) (loop while xs for x = (reduce #'min xs) do (setq xs (remove x xs :count 1)) collect x))

So **loop** isn't always more concise than the standard lisp alternative.

### Selection sort (19)

**Faré** suggested you can reduce the size by replacing:

`(if (null lst) nil ...`

with

(and lst ...

Although this saves two tokens it only reduces the score by 1 because **count-atoms** ignores nil.

So the best answer so far is:

(defun mysort (lst) (and lst (let ((min (reduce #'min lst))) (cons min (mysort (remove min lst :count 1))))))

### Merge sort (27)

Although efficiency wasn't a consideration of the original challenge **Faré** provided a more efficient merge sort with N log N speed and a score of 27:

(defun mysort (l)

(let ((half (ash (length l) -1)))

(if (zerop half) l

(merge (type-of l)

(mysort (subseq l 0 half))

(mysort (subseq l half)) '<))))

### Insertion sort (16)

Finally leaving the best to last; the previous solution suggested the following, which has the best score of 16 (until someone beats it!):

(defun mysort (lst) (and lst (merge 'list (list (car lst)) (mysort (cdr lst)) #'<)))

It places each element at the correct position in the sorted list of elements processed so far. It relies on the fact that if **merge** is given two lists that are already sorted by the predicate the result is a sorted list. A list of one element is trivially already sorted, and the list returned by the recursive call to **mysort** is also, by definition, already sorted; QED.

blog comments powered by Disqus