Page History

...

• (20 pts) Write the same mergesort function as described in exercise 26.1.2, except decompose the problem "top-down" rather than "bottom-up". You will need to define a function split: (list-of number) -> (list2-element-structure-of (-list-of number)) that partitions its input into two lists of approximately (+/- 1) the same length in O(n) time where n is the length of the input list. (split l) returns a list a structure containing two lists of numbers. See below for hints in defining a 2-element structure.  After splitting the list in half, mergesort recursively sorts each half and then merges them together.

A 2-element structure can be defined (you MUST do this somewhere!) in one of two ways:
a)  Define your own structure.   The CS term for a pair of elements is "dyad", so for instance, one could define a structure as

(define-struct dyad (first second)) 

Review your notes on how "define-struct" automatically creates constructor and accessor functions.    You will still need to, in words, define what types the "first" and "second" elements are supposed to be (note: there are several ways to do this). 

b) Use Scheme's built-in functions.    First, you must explicitly define that you are going to use a list of exactly two elements, i.e. "(list a b)".    Scheme already provides functions to access the first and second elements of such a list, oddly enough, called "first" and "second":

(first (list a b)) ==> a

(second (list a b)) ==> b 

Again, you will still need to define exactly what types the first and second elements are supposed to be.