(a) Assume that we have a list L of integers. Define a function (listify L) that divides L into one or more sublists so that each sublist contains integers in non-decreasing (sorted) order. That is if v1 and v2 are adjacent in L and v1 <= v2 then v1 and v2 are adjacent in the same sublist. However, if v1 > v2 then v1 ends one sublist and v2 begins the next sublist. For example.
(listify '(3 5 1 8 9 2 1 0)) ---> ((3 5) (1 8 9) (2) (1) (0)) (listify '(1 2 3 4 5 6)) ---> ((1 2 3 4 5 6)) (listify '(5 4 3 2 1)) ---> ((5) (4) (3) (2) (1))
(b) If the output of listify contains a single sublist, then we know the input list L was in sorted order. Otherwise, we can implement a merge-sort-like sorting algorithm as follows. Take the first two sublists produced by listify and merge them into a single sorted list. Then take the next two sublists and merge them. Repeat until all sublists are considered. (The last sublist is copied unchanged if it has no partner to merge with). If only one sublist remains, we are done. Otherwise, we repeat the process, merging sublists pairwise. At each stage, the number of sublists is cut in half. For example,
((3 5) (1 8 9) (2) (1) (0)) is reduced to
(1 3 5 8 9) (1 2) (0)) and then to
((1 1 2 3 5 8 9) (0)) and finally to
((0 1 1 2 3 5 8 9)).
Implement (merge-sort L), which sorts the values in L using listify as a subroutine. The function merge-sort should accept a list of integers, and return a list of integers in order. For example:
(merge-sort '(3 5 1 8 9 2 1 0)) ---> (0 1 1 2 3 5 8 9)
(c) It is sometimes the case that a sorted list should contain no duplicate values. Modify your implementation of merge-sort so that if it sees two duplicate values it immediately returns the pair (duplicate.val) instead of the sorted list. duplicate is a fixed symbol; val is the duplicate value that was seen in L. Hence (duplicate.17) would indicate that 17 was duplicated in L.
Note that you should not check for duplicates after the sort is done, or as a preprocessing step before the sort has started. Duplicate checking should be integral to your implementation of listify and the merge component of your merge sort. You should use call/cc to implement the exception mechanism you will need to return a duplicate value.
You should only turn in the code you write for part (c) if you succeed. Otherwise, turn in your code for parts (a) and (b). Indicate in program comments what level of functionality you were able to achieve.
You must use recursion, and not iteration. You may not use side-effects (e.g. set!).
Submit your code in a file called mergesort.scm.