This homework concerns sorting and binary search; most code is provided but requires modification on your part.

[25 points] We have discussed the benefits of merge sort; in particular, it has asymptotically good running time. However, for small arrays, other sorting algorithms outperform it because their work per comparison is lower. Modify a string merge sort to use insertion sort to sort sublists (partitions) that are of length five or less; that is, when merge sort is called with an array A and A.length < 5, call insertion sort to sort the array instead of continuing merge sort's divide-and-conquer strategy. ~lorenz/cs35-2/algorithms/sorts/ contains various sorting algorithms including merge and insertion sorts for strings.

Test your code on an array containing at least 20 strings.

[25 points] Modify a binary search to use recursion instead of a loop. A loop-based binary search is available in ~lorenz/cs35-2/algorithms/searches/; study it. (For an example of recursion, recall the merge-sort code that calls merge sort to sort the partitions.) The signature of your search might be:

public static int binary(String s, String[] A, int low, int high);

where low/high denotes the range in the array A to search. Your recursive search might be implemented as follows. If the sought element is not at the mid position, compute new low/high values and call your search recursively. Terminate the recursion when the range no longer contains elements.

Test your program. The main method provided with the binary search can serve this purpose.

Hand in: complete code and comments for parts one and two. Hand in scripts that demonstrate that your sort and search programs work.
instructions on how to submit