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) -> 2-element-structure-of-lists-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 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.

Hints for writing the "split" function: 

A 2-element structure can be defined (you MUST do this somewhere!) in one of two ways:

...

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

Think simple!
Follow these important rules whenever you write function on a list:

• Write down and follow the list function template!
• Think about what can be done with what your template says you have to work with, namely,

  Code Block
  (first aList)

  and the recursive result,

  Code Block
  (myFunction (rest aList))

  .
• Use a

  Code Block
  local

  definition to keep you from repeating the recursive call.