Racket: Using recursion to make a mergesort function

Question

I have a Racket homework problem that asks me to create a mergesort function using recursion. It is supposed to take a list, split it up into smaller lists, and then sort them from least to greatest. The function is also supposed to return that sorted list without using any sorting commands in this assignment.

This is the code I have so far:

(define (mergesort lst)
  (cond
    [(empty? lst) '()]
    [(= (length lst) 1) lst]
    [(let* ([index 0][end_index (- (length lst) 1)])
       (if (< (list-ref lst index) (list-ref lst (add1 index)))
           (cons...)
           (cons...) 
           ))]
    )
  )

(mergesort '(3 1 2 7 9)) ;should return (1 2 3 7 9)

I am struggling with figuring out how to move the elements into their proper position (from least to greatest) when the if statement is met. Am I on the right track?

Answer 1

To split a list into two sublists, you can use functions take and drop. For example:

> (define L '(5 9 1 3 7 0 8 4 6 2))

> (take L 5) ; get the first 5 elements in L
'(5 9 1 3 7)

> (drop L 5) ; skip the first 5 elements in L and get the rest
'(0 8 4 6 2)
> 

Given two sorted lists, the following function returns a sorted list containing all elements from both lists:

(define (merge A B)
    (cond [(empty? A) B]
          [(empty? B) A]
          [(<= (first A) (first B)) (cons (first A) (merge (rest A) B))]
          [else                     (cons (first B) (merge A (rest B)))]))

For example:

> (merge '(0 1 3 6 7) '(2 4 5 8 9))
'(0 1 2 3 4 5 6 7 8 9)

Thus, the merge-sort algorithm can be coded as follows:

(define (merge-sort L)
  (let ((k (quotient (length L) 2)))
    (cond [(zero? k) L]
          [else (merge (merge-sort (take L k))
                       (merge-sort (drop L k)))])))

Example:

> (merge-sort '(5 9 1 3 7 0 8 4 6 2))
'(0 1 2 3 4 5 6 7 8 9)
>