...
- (20 pts) Write the same
mergesortfunction as described in exercise 26.1.2, except decompose the problem "top-down" rather than "bottom-up". You will need to define a functionsplit: (list-of number) -> 2-element-structure-of-listlists-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,mergesortrecursively 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
...