Ordena.lsp

(define (ordena-lista l)
    (if (or (null? l)
	              (null? (cdr l)))
            l
	          (let ((p (car l)))
		            (let ((clas (clasifica p l)))
			                (append (ordena-lista (first clas)) 
						                  (second clas)
								                    (ordena-lista (third clas)))))))

(define (clasifica ref lista)
    (clasifica-aux () () () ref lista))

(define (clasifica-aux menores iguales mayores ref lista)
    (if (null? lista)
            (list menores iguales mayores)
	          (let ((valor (car lista)))
		            (cond ((< valor ref) 
				                  (clasifica-aux (cons (car lista) menores) iguales mayores ref (cdr lista)))
				                ((< ref valor)
						                (clasifica-aux menores iguales (cons (car lista) mayores) ref (cdr lista)))
						              (else 
								               (clasifica-aux menores (cons (car lista) iguales) mayores ref (cdr lista)))))))

(define (lista long talla) ;; construye una lista de numeros en el intervalo [0,talla) de longitud long 
  (if (= long 0)
          ()
	        (cons (random talla) (lista (- long 1) talla))))

(define l1 (lista 1000 1000000))
(time (ordena-lista l1) 9)

(define l2 (lista 2000 1000000))
(time (ordena-lista l2) 9)

(define l3 (lista 4000 1000000))
(time (ordena-lista l3) 9)

(define l4 (lista 8000 1000000))
(time (ordena-lista l4) 9)