MergeList

Background:

An unordered linked list is difficult to sort given its sequential nature, but a recursive merge sort works well for linked lists. The algorithms required (split and merge) will provide excellent practice in working with the java.util.LinkedList and ListIterator classes.

Here are the three steps for a recursive merge sort:

1. Split the list into two smaller lists.
2. Recursively sort each of these lists using merge sort.
3. Merge the two sorted lists together.

Review the merge sort concept and code from the lecture (or book, chapter 13) to help you to implement the same concept with linked lists.

Assignment:

1. The linked list should be of type java.util.LinkedList.

2. The data file to be used in this lab is (file20.txt).

3. Build the initial linked list from (file20.txt) following this logic:

   place each new Id/Inv pair that is read from the data file at the beginning of the list

   Therefore, the first values read from the data file will end up last in the list.

4. The recursive merge sort algorithm will need the supporting algorithms of splitting and merging lists. List iterators should be used to implement these methods.

5. Your program should consist of the following sequence of scripted events:

   - Load the data file and build the initial list
   - Print the linked list - it is unordered
   - Recursively merge sort the list
   - Print the linked list - it is now sorted
   - Reverse the linked list
   - Print the linked list - it is now in descending order

6. If your teacher so chooses, you will be provided with a program shell consisting of a MergeList class containing a main method, and the Item class. All of the code development will be in the MergeList class.

Instructions:

1. Modify and write code as necessary to satisfy the above specifications.

2. Print out the source for the MergeList class.

3. Turn in your source code along with the run output.