Question

Please answer this multi-part question. Thank you!

For this assignment you must write the following function in Scheme:

4 Write a recursive function called mergesort that sorts a list by doing the following:
(a) Use split to split the list into two roughly equal-sized partitions.
(b) Recursively sort both partitions.
(c) Use merge to merge the sorted partitions together.
Once again you will need two base cases, one for the empty list and the other for a single-element list.
> (mergesort '())

()

> (mergesort '(9))

(9)

> (mergesort '(8 6 7 5 3 0 9))

(0 3 5 6 7 8 9)

Answer 1

;; Exp. (merge '(1 3 5 7 8 9 10) '(2 4 6)) ==> (1 2 3 4 5 6 7 8 9 10) (define (merge L M) (if (null? L) M (if (null? M) L (if (< (car L) (car M)) (cons (car L) (merge (cdr L) M)) (cons (car M) (merge (cdr M) L)))))) ;; split helper functions (define (odd L) (if (null? L) '() (if (null? (cdr L)) (list (car L)) (cons (car L) (odd (cddr L)))))) (define (even L) (if (null? L) '() (if (null? (cdr L)) '() (cons (cadr L) (even (cddr L)))))) ;; Exp. (split '(a b c d e f g h i)) ==> ((a c e g i)(b d f h)) (define (split L) (cons (odd L) (cons (even L) `()))) ;; Exp. (mergesort '(8 1 3 9 6 5 7 2 4 10)) ==> (1 2 3 4 5 6 7 8 9 10) (define (mergesort L) (if (null? L) L (if (null? (cdr L)) L (merge (mergesort (car (split L))) (mergesort (cadr (split L)))))))
	(if (null? L) M
	(if (null? M) L
	(if (< (car L) (car M))
	(cons (car L) (merge (cdr L) M))
	(cons (car M) (merge (cdr M) L))))))
	;; split helper functions
	(define (odd L)
	(if (null? L) '()
	(if (null? (cdr L)) (list (car L))
	(cons (car L) (odd (cddr L))))))
	(define (even L)
	(if (null? L) '()
	(if (null? (cdr L)) '()
	(cons (cadr L) (even (cddr L))))))
	;; Exp. (split '(a b c d e f g h i)) ==> ((a c e g i)(b d f h))
	(define (split L)
	(cons (odd L) (cons (even L) `())))
	;; Exp. (mergesort '(8 1 3 9 6 5 7 2 4 10)) ==> (1 2 3 4 5 6 7 8 9 10)
	(define (mergesort L)
	(if (null? L) L
	(if (null? (cdr L)) L
	(merge
	(mergesort (car (split L)))
	(mergesort (cadr (split L)))))))