Page History

...

• 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) -> (listof (listOf list-of (list-of number)) that partitions its input into two lists of approximately (+/- 1) the same length in O time where n is the length of the input list. (split l) returns a list containing two lists of numbers. After splitting the list in half, mergesort recursively sorts each half and then merges them together.