#lang racket ;;; Split a list into two sublists of approximately the same length, ;;; returned as a list of these two result lists (define (split lst) (cond ((null? lst) (list '() '())) ((null? (cdr lst)) (list lst '())) (#t (let* ((subsplit (split (cdr (cdr lst)))) (lst1 (car subsplit)) (lst2 (car (cdr subsplit)))) (list (cons (car lst) lst1) (cons (car (cdr lst)) lst2)))))) ;;; Merge two sorted lists of numbers into one sorted list (define (merge lst1 lst2) (cond ((null? lst1) lst2) ((null? lst2) lst1) (#t (if (< (car lst1) (car lst2)) (cons (car lst1) (merge (cdr lst1) lst2)) (cons (car lst2) (merge lst1 (cdr lst2))))))) ;;; Sort a list (of numbers) using the merge-sort algorithm (define (mergesort lst) (if (or (null? lst) (null? (cdr lst))) lst (let* ((splt (split lst)) (srt1 (mergesort (car splt))) (srt2 (mergesort (car (cdr splt))))) (merge srt1 srt2)))) (split '()) (split '(1)) (split '(1 2)) (split '(1 2 3 4 5 6 7)) (split '(1 2 3 4 5 6 7 8)) (merge '() '()) (merge '(1) '()) (merge '() '(1)) (merge '(1 3 5) '(2 4 6)) (merge '(1 3 5) '(1 3 5)) (display "Sorting")(newline) (mergesort '()) (mergesort '(1)) (mergesort '(1 3 2 5 9 2))