Project 4: Merge sort

The goal of this project is to practice using recursion on a sophisticated algorithm.

1. Setup

As, usual, move into your cs235 directory, clone the repository to make a directory for this assignment, and change into it.

$ cd cs235
$ hg clone /cslab/class/csci235/projects/project4
$ cd project4

What you'll find there are two files: the driver Sort.java from the last project and a new file Merge.java that contains the stubs for this project.

2. Merge Sort

The final sort works this way: Suppose you have an unsorted pile of cards in your hand. First you split that pile up into two smaller piles. Then you sort each pile. Finally, you merge the two smaller (now sorted) piles into a full, sorted pile. This raises the question, how do we sort the smaller piles? The answers is—the same way we sort the big one: we split those up each into two even smaller piles, sort those smaller piles, and merge them into a sorted small pile. We repeat the process (recursively) until we get to a pile of size 1, which is trivially sorted.

This sort is more efficient than the other three sorts in its use of time (ie, it's faster), but less efficient in its use of space, since this is not an "in-place" sort. It will use helper arrays to store some of the data temporarily.

We break down the task of writing this sort into a few manageable pieces—each "piece" will involve writing a method. You should test these pieces individually by writing a main method for this file to test the individual methods. You will not be graded for the main method (in fact, you may delete it before turning the project in), but you will have an easier time with this if you test the pieces as you go. For example, the first piece is to write a method that will make an array from a portion of another array; you should test this by making an array, printing it out, calling the method you've written on that array, and printing out what the method returns.

A. Making a subarray

Recall the String method substring(). Now we want to write a method that works similarly for arrays. Fill-in the body for the method subArray(). It should take an array, and starting index (inclusive), and a stopping index (exclusive); it should create a new array the size of the range specified (stop - start) and copy the elements from the given array to the new array; and return the new array. Test to make sure this works.

B. Merging two sorted arrays

Next, we want to write a method that takes two arrays—which it assumes to be already sorted—and creates a new array—the size of the two given arrays combined—and fills the new array with the elements from the two. For example, given {2, 6, 8, 9} and {3, 4, 5, 10}, it should return an array {2, 3, 4, 5, 6, 8, 9, 10}. This is tricky. Think carefully about this, fill-in the body of merge(), and test.

C. The merge sort algorithm

Now, we want to implement the actual merge sort algorithm. This will be in the body of mergeSort(). This method receives and array; it should (1) split the array into two arrays representing its halves (using subarray()) (2) sort each half (using mergeSort()) recursively (3) merge the result of each half together using merge() (4) return the result of merge().

D. Making it work as if it were in-place

The problem with what we have so far is that our driver program expects the sort methods to be in-place sorts. It just passes an array and expects the method to mutate it. We can simulate this by writing the sort() method so that it (1)calls mergeSort() on the given array, storing the result in another variable (2) copying the elements from the result array back into the given array. Fill-in sort() so that it works that way.

3. Turn in

Create the script file as before (compile and run). Run each sort a couple of times.

Hand in your Merge.java and your typescript as project4.

DUE: Tues., Oct. 14, at 5:00 PM.