Insertion sort in place LISP

Question

I'm still pretty new to proper Lisp and I'm trying to build a simple, yet at least a bit efficient insertion sort - I would like to switch elements in place, but still have an ability to append to my container afterwards. I took my old C++ implementation:

template<typename Iter>
void insertionSort(Iter begin, Iter end){
    for (auto i = begin; i != end; ++i){
        for (auto j = i; j != begin && *(std::prev(j)) > *(j); j--){
            std::iter_swap(j, std::prev(j));
        }
    }
}

And created the following code (taking into account that aref and rotatef have fair complexity), but it does not seem to take any effect on the input (UPD: now it simply works improperly), what might be wrong with my solution? I'm returning for testing purposes, should I create a macro in order to avoid pass-by-value?

(defparameter testa (make-array 4 :initial-contents '(2 3 1 5)))
(defun insertion-sort (vect)
    (loop for i from 0 to (1- (length vect)) do
        (loop for j from i downto 0
            until (or (= (1- j) -1) (> (aref vect (1- j)) (aref vect j)))
            do (rotatef (aref vect i) (aref vect (1- j))))
    )
    vect
)
(format t "~a~%" (insertion-sort testa))

UPD: updated the code based on the comments from @jkiiski and @RainerJoswig, the output is still wrong.

Answer 1

In your program there are several problems.

First, the sort does not work since the line:

do (rotatef (aref vect i) (aref vect (1- j))))

should be:

do (rotatef (aref vect j) (aref vect (1- j))))

that is, you have written the variable i instead of j

If you make this correction, you will find that the order is decreasing (I assume that you want an increasing order). This depends on the use of until instead of while.

Finally, there is redundant code. A more simple and efficient version is the following:

(defparameter testa (make-array 4 :initial-contents '(2 3 1 5)))
(defun insertion-sort (vect)
   (loop for i from 1 below (length vect) 
     do (loop for j from i above 0
          while (> (aref vect (1- j)) (aref vect j))
          do (rotatef (aref vect j) (aref vect (1- j)))))
   vect)
(format t "~a~%" (insertion-sort testa))

This parallel the pseudo-code in the wikipedia page of Insertion sort.

If you want to parameterize the sorting predicate, as well as add an optional keyword-based “key” parameter to the function, here is a possible solution:

(defun insertion-sort (vect predicate &key (key #'identity))
  (loop for i from 1 below (length vect) 
        do (loop for j from i above 0
                 while (funcall predicate 
                                (funcall key (aref vect (1- j)))
                                (funcall key (aref vect j)))
                 do (rotatef (aref vect j) (aref vect (1- j)))))
         vect)

CL-USER> (insertion-sort testa #'>)
#(1 2 3 5)
CL-USER> (insertion-sort testa #'<)
#(5 3 2 1)

CL-USER> (defparameter testa (make-array 4 :initial-contents '((c 3) (d 2) (b 1) (a 4))))
TESTA
CL-USER> (insertion-sort testa #'string> :key #'car)
#((A 4) (B 1) (C 3) (D 2))