The purpose of this lab is to give you experience with using recursion to solve problems. You will also have a chance to use arrays. Note that in this lab you will be graded on your ability to simplify the problem by using recursion, not just on your completion of the problem. You should focus on using methods to abstract away complexity as well as using recursion.

Imagine you are developing a contact list application for a mobile device. One of the functions you will likely need is a function which can take a list of names and put them in order. For this lab you will do precisely that:

1. prompt the user for the name of a file containing a list of names
2. read in the specified file
3. sort them in alphabetical order (by first and then last name), and
4. print them to an output file (you can hardcode the name or prompt the user for a name).

The data file will look something like this:

Minnie Mouse
Scrooge McDuck
Donald Duck
Mickey Mouse
Max Goof

You should display the data in sorted order:

Donald Duck
Max Goof
Mickey Mouse
Minnie Mouse
Scrooge McDuck

You will want to use an array to store the names. See section 6.1 of the book for information on using arrays. For our purposes, you can assume that we will never have more than 100 names.

To sort the list of names you will use an algorithm called a merge sort which by nature requires a recursive implementation. The algorithm essentially works by recursively splitting a list into sublists and then recombining the sorted sublists. See the link to wikipedia for more information about how the merge sort algorithm works.

The key to recursive programming is in thinking about a way to solve the problem using a smaller version of the same problem. So, if you think about sorting, consider solutions where you sort a part of the list and then assume the rest is sorted in order to create a fully sorted list.

Make sure you use methods to solve parts of the problem so that the overall problem is not so complex.

Some useful functions:

• Look at page 88 in the text for a good description of string comparison.
• str.compareTo(str) (also look at the compareToIgnoreCase method)
• array.length

Keep in mind that when java compares strings, an upper case letter will always be “greater” than a lower case letter. Thus 'A' is greater than 'z' but less than 'Z'.

Decomposing the problem using methods will make your code easier to read, easier to debug, and in some cases shorter. Aside from preventing code duplication, creating your own method allows you to create a single, clear command from multiple obscure commands, thereby making it easy to see what your code should be doing. A good way to identify when it is appropriate to create a method is if you see a block of 5-10 lines of code that all work to accomplish a single task. For example, finding the index in an array which contains the lowest string. Recursion will inherently require you to create at least one method, but using methods in general is a very good habit to get in to.

You will prompt the user for the needed file name. You will need to create your own test files in order to assure that your code is working. We have created a wiki page with information about where to put files in order for your eclipse program to find them.

Just as when you were scanning websites, java will want you to deal with the possibility that the Scanner object cannot find the specified file. To resolve the error you will notice that Eclipse gives you two alternatives: add a throws statement or surround with try/catch. For now you can simply throw the error rather than the try/catch alternative. TAs will only run real file paths on your code.

When you have your program working, you will need to show it to a TA. The TA will evaluate your code based on the following criteria:

1. Show the TA your test cases, with the input and correct output (manually written). You will be graded on the diversity of your tests. You should have about 5-10 tests (different files). Consider border cases (e.g. a list with one name, a list with 2 of the same name, two with the same first name but different last name, etc.) (5 points)
2. Prompt the user for the name of file containing names. (5 points)
3. Use an array to store the names. You can use other data structures as well, but at least one data structure needs to be an array. (5 points)
4. Sort the data correctly and write it to an output file. (10 points)
5. Effectively use recursion by implementing merge sort (15 points)
6. Is your code properly formatted (indenting blocks, comments, spacing, reasonable names of variables)? (5 points)

Extra Credit: Prompt user for option of doing a reverse sort (i.e. z to a) (2 points)

Extra Credit: Sort by last name and then first name (3 points)