; Question 1
; implement the insertion sort in scheme
(define insert
    (lambda (ls1 ls2)
        (if (null? ls1)
            ls2
            (if (null? ls2)
                ls1
                (if (< (car ls1) (car ls2))
                    (cons (car ls1) (insert (cdr ls1) ls2))
                    (cons (car ls2) (insert (cdr ls2) ls1)))))))

(define insertion-sort
    (lambda (ls)
	(if (null? ls) '()
        (insert (list (car ls)) (insertion-sort (cdr ls))))))
        
; Question 2
; Implement the merge sort in scheme

(define merge
    (lambda (ls1 ls2)
        (if (null? ls1)
            ls2
            (if (null? ls2)
                ls1
                (if (< (car ls1) (car ls2))
                    (cons (car ls1) (merge (cdr ls1) ls2))
                    (cons (car ls2) (merge (cdr ls2) ls1)))))))

(define odd
    (lambda (ls)
        (if (null? ls) '()
            (if (null? (cdr ls)) (list (car ls))
                (cons (car ls) (odd (cddr ls)))))))
            
(define even
    (lambda (ls)
        (if (null? ls) '()
            (if (null? (cdr ls)) '()
                (cons (cadr ls) (even (cddr ls)))))))

(define split
    (lambda (ls)
	    (cons (odd ls) (cons (even ls) `()))))

(define merge-sort
    (lambda (ls)
        (if (null? ls)
            ls
            (if (null? (cdr ls))
                ls
                (merge
                    (merge-sort (car (split ls)))
                    (merge-sort (cadr (split ls))))))))