Question

This problem should be solved using the DrRacket software in Racket/Scheme language.

Write a function (merge-sorter L1) that takes list-of-integers L1 and returns all elements of L1 in sorted order. You must use a merge-sort technique that, in the recursive case, a) splits L1 into two approximately-equal-length lists, b) sorts those lists, and then c) merges the lists to obtain the result. See the following examples for clarificaton.

(merge-sorter '(3 1 5 4 2) ---> (1 2 3 4 5)
(merge-sorter '()) ---> ()
(merge-sorter '(1)) ---> (1)

Answer 1

Code:

;;sample: (merge-lists '(6 9 11 13) '(7 10 12)) => '(6 7 9 10 11 12)
(define (merge-lists L1 L2) ;;Merges two lists which are already in sorted order
   (cond ((null? L1) L2)
   ((null? L2) L1)
   ((< (car L1) (car L2)) (cons (car L1) (merge-lists (cdr L1)L2)))
   (else (cons (car L2) (merge-lists (cdr L2) L1)))))

;; helper functions of split function
(define (odd List) ;;returns the list of elements which are in odd position
   (cond ((null? List) '())
   ((null? (cdr List)) (list (car List)))
   (else (cons (car List) (odd (cddr List))))))

(define (even List) ;;returns the list of elements which are in even positions
   (cond ((null? List) '())
   ((null? (cdr List)) '())
   (else(cons (cadr List) (even (cddr List))))))

;; sample: (split '(8 9 12 17 18)) ==> ((8 12 18)(9 17))
(define (split List) ;;returns list of two sublists 1)odd position elements list 2) even position elements list
   (cons (odd List) (cons (even List) '())))

;;MAIN_FUNCTION
(define (merge-sorter List) ;;returns list of elements in increasing order
   (cond ((null? List) '()) ;;if list is empty returns empty list
   ((null? (cdr List)) List) ;;if list has only one element return that element
   (else (merge-lists
           (merge-sorter (car (split List))) ;;else merge two sorted lists which are splitted
           (merge-sorter (cadr (split List)))))))

Snapshot of Code and Output: