Sort 3 numbers in Common Lisp with the minimum number of operations

Question

I’m wondering is the following function returns a list of three numbers sorted in ascending order with the minimum possible number of operations, or if there is some more efficient or elegant method (a part from using the primitive function sort!)

(defun order (min mid max)
"sort three numbers in ascending order"
 (when (< mid min)
 (rotatef mid min))
 (if (< max min)
 (rotatef max mid min)
 (when (< max mid)
 (rotatef mid max)))
 (list min mid max))

With "minimum possible number of operations" I mean that the function should solve the problem with a number of tests and assignments (rotatef swaps two variables or rotates three or more variables) which is the minimum on the average on all the possible cases.

Answer 1

It does seem to be correct. As for elegance, I believe it can be expressed without nested conditionals and I would consider that more elegant, even if it takes the average number of comparisons from 2.5 to 3. This code does 3 comparisons (always) and up to six writes. Your code does 2 or 3 comparisons and up to seven writes (ignoring temps, that would take the code below to "up to nine" and your code to "up to ten").

On the balance, your code probably has a slight edge in performance, so if this would be a frequently-called function, I would consider using order over order3.

That is:

(defun order3 (min mid max)
 (when (< max min)
 (rotatef max min))
 (when (< mid min)
 (rotatef mid min))
 (when (< max mid)
 (rotatef max mid))
 (list min mid max))

• Renzo: Thanks for the answer! I made some tests in CCL and order3 is only 6% slower than order. So a very small loss of efficiency with an increase in readability.