Insertion sort in Common Lisp
Trivial

Use 1- instead of (- ... 1).

Avoid very long lines (Emacs will indent for you).

Do not use cond when a single if without progn would do.

Memory

Use nconc instead of
append when possible to avoid
unnecessary consing (in your case, splice allocates a fresh list, so
its result can be passed to nconc).

Catastrophic

Whenever you use nth, you are
using the wrong algorithm.

Optimal search is linearithmic: O(n*log(n)).

Insert search is quadratic: O(n^2).

Your implementation is O(n^3):


nth is O(n)
slice is O(n^2) (calls nth * recursion).
splice and move are also O(n^2) (call slice).
find-ordered-index is O(n).
insertion-sort is O(n^3) (calls move * recursion).