Insertion Sort in Common lisp

I want to implement the sorting function in common-lisp with this INSERT function k means cons cell with number & val, and li means list where I want insert k into. with this function, I can make a list of cell

(defun INSERT (li k)  (IF (eq li nil) (cons (cons(car k)(cdr k)) nil)
    (IF  (eq (cdr li) nil)
          (IF (< (car k)(caar li))  (cons (cons(car k)(cdr k)) li)
            (cons (car li)  (cons (cons(car k)(cdr k)) (cdr li)) )
          )
        (cond 
            (    (eq (< (caar li) (car k)) (< (car k) (caadr li)) ) 
               (cons  (car k)  (cons (cons (car k) (cdr k))  (cdr li))  )   )
            (t (cons (car li) (INSERT (cdr li) k))  )))))

and what I want is the code of this function below. it has only one parameter li(non sorted list)

(defun Sort_List (li)(...this part...))

without using assignment, and using the INSERT function

Solution

Your insert function is very strange. In fact I find it so hard to read that I cn't work out what it's doing except that there's no need to check for both the list being null and its cdr being null. It also conses a lot of things it doesn't need, unless you are required by some part of the specification of the problem to make copies of the conses you are inserting.

Here is a version of it which is much easier to read and which does not copy when it does not need to. Note that this takes its arguments in the other order to yours:

(defun insert (thing into)
  (cond ((null into)
         (list thing))
        ((< (car thing) (car (first into)))
         (cons thing into))
        (t (cons (first into)
                 (insert thing (rest into))))))

Now, what is the algorithm for insertion sort? Well, essentially it is:

loop over the list to be sorted:
- for each element, insert it into the sorted list;
- finally return the sorted list.

And we're not allowed to use assignment to do this.

Well, there is a standard trick to do this sort of thing, which is to use a tail-recursive function with an accumulator argument, which accumulates the results. We can either write this function as an explicit auxiliary function, or we can make it a local function. I'm going to do the latter both because there's no reason for a function which is only ever used locally to be globally visible, and because (as I'm assuming this is homework) it makes it harder to submit directly.

So here is this version of the function:

(defun insertion-sort (l)
  (labels ((is-loop (tail sorted)
             (if (null tail)
                 sorted
               (is-loop (rest tail) (insert (first tail) sorted)))))
    (is-loop l '())))

This approach is fairly natural in Scheme, but not very natural in CL. An alternative approach which does not use assignment, at least explicitly, is to use do. Here is a version which uses do:

(defun insertion-sort (l)
  (do ((tail l (rest tail))
       (sorted '() (insert (first tail) sorted)))
       ((null tail) sorted)))

There are two notes about this version.

First of all, although it's not explicitly using assignment it pretty clearly implicitly is doing so. I think that's probably cheating.
Secondly it's a bit subtle why it works: what, exactly, is the value of tail in (insert (first tail) sorted), and why?

A version which is clearer, but uses loop which you are probably not meant to know about, is

(defun insertion-sort (l)
  (loop for e in l
        for sorted = (insert e '()) then (insert e sorted)
        finally (return sorted)))

This, however, is also pretty explicitly using assignment.

As Kaz has pointed out below, there is an obvious way (which I should have seen!) of doing this using the CL reduce function. What reduce does, conceptually, is to successively collapse a sequence of elements by calling a function which takes two arguments. So, for instance

(reduce #'+ '(1 2 3 4))

is the same as

(+ (+ (+ 1 2) 3) 4)

This is easier to see if you use cons as the function:

>  > (reduce #'cons '(1 2 3 4))
(((1 . 2) . 3) . 4)

> (cons (cons (cons 1 2) 3) 4)
(((1 . 2) . 3) . 4)

Well, of course, insert, as defined above, is really suitable for this: it takes an ordered list and inserts a new pair into it, returning a new ordered list. There are two problems:

my insert takes its arguments in the wrong order (this is possibly why the original one took the arguments in the other order!);
there needs to be a way of 'seeding' the initial sorted list, which will be ().

Well we can fix the wrong-argument-order either by rewriting insert, or just by wrapping it in a function which swaps the arguments: I'll do the latter because I don't want to revisit what I wrote above and I don't want two versions of the function.

You can 'seed' the initial null value by either just prepending it to the list of things to sort, or in fact reduce has a special option to provide the initial value, so we'll use that.

So using reduce we get this version of insertion-sort:

(defun insertion-sort (l)
  (reduce (lambda (a e)
            (insert e a))
          l :initial-value '()))

And we can test this:

>  (insertion-sort '((1 . a) (-100 . 2) (64.2 . "x") (-2 . y)))
((-100 . 2) (-2 . y) (1 . a) (64.2 . "x"))

and it works fine.

So the final question the is: are we yet again cheating by using some function whose definition obviously must involve assignment? Well, no, we're not, because you can quite easily write a simplified reduce and see that it does not need to use assignment. This version is much simpler than CL's reduce, and in particular it explicitly requires the initial-value argument:

(defun reduce/simple (f list accum)
  (if (null list)
      accum
    (reduce/simple f (rest list) (funcall f accum (first list)))))

(Again, this is not very natural CL code since it relies on tail-call elimination to handle large lists, but it makes the point that you can do this without assignment.)

And so now we can write one final version of insertion-sort:

(defun insertion-sort (l)
  (reduce/simple (lambda (a e)
                   (insert e a))
                 l '()))

And it's easy to check that this works as well.