Sortare prin insertie in Scheme

In Scheme, o sortare se realizeaza in doua etape:
- se creeaza o functie simpla insert care adauga un element intr-o lista deja sortata. Merge pe principiul: ia o lista, verifica primul element, daca e mai mare decat elementul de inserat acesta se va insera chiar inaintea lui, altfel listei i se aplica `tail`, iar listei ce rezulta fara primul element i se aplica acelasi tratament pana cand elementul de inserat isi gaseste locul in lista (recursivitate).
- se creeaza o lista vida in care se vor insera pe rand fiecare element din lista noastra.

(define insert ; insereaza un element intr-o lista deja sortata

(lambda (element lista)

(cond ((null? lista) (list element)) ; daca e lista nula creeaza o noua lista din element

((<= element (car lista)) (cons element lista)) ; daca elementul<=primul element din lista, il pune primul

(else (cons (car lista) (insert element (cdr lista))))))) ; altfel lipeste primul element de restul listei unde element se presupune a fi inserat

(define ls '(20 51 19 13 10))

(define ls_empty '())

(define insertion-sort

(lambda (ls new)

(if (null? ls) new

(let ((new (insert (car ls) new))) (insertion-sort (cdr ls) new))

)

))

(insertion-sort ls ls_empty)