Question

Hello. Please answer the following question in Scheme. Not Python, not any form of C, but in the language Scheme. If you do not know Scheme, please do not answer the question. I've had to upload it multiple times now. Thank you.

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

Algorithm Expalined:

;; Merge two sorted lists into a single sorted list
(define (merge list1 list2)
  (cond
    ((null? list1)
     list2)
    ((null? list2)
     list1)
    (else
      (let ((head1 (car list1))
            (head2 (car list2)))
        ; Add the smaller element to the front of the merge list
        (if (<= head1 head2)
          (cons
            head1
            ; Recursively merge
            (merge (cdr list1) list2))
          (cons
            head2
            ; Recursively merge
            (merge list1 (cdr list2))))))))

(define (split-list lst)
  (let ((half (quotient (length lst) 2)))
    ; Create a pair of the first and second halves of the list
    (cons
      (take lst half)
      (drop lst half))))

(define (merge-sort lst)
  (cond
    ((or (null? lst) ; empty list is sorted, so merge up
         (null? (cdr lst))) ; single-element list is sorted, so merge up
     lst)
    (else
      (let ((halves (split-list lst)))
        ; Recursively split until the bottom, then merge back up to sort
        (merge (merge-sort (car halves))
               (merge-sort (cdr halves)))))))

Solution With your example

;; Exp. (mergesort '(8 6 7 5 3 0 9)) ==> (0 3 5 6 7 8 9)
(define (mergesort L)
        (if (null? L) L
                (if (null? (cdr L)) L
                        (merge
                                (mergesort (car (split L)))
                                (mergesort (cadr (split L)))))))