Background:
An unordered linked list is difficult to sort given its sequential nature, but a recursive merge sort can be developed for linked lists. The algorithms required (split and merge) will provide excellent practice in working with the java.util.LinkedList
and ListIterator
classes.
A linked list can be sorted using a recursive merge sort algorithm. Here are the steps:
- Split the list into two smaller lists.
- Recursively sort these two lists using merge sort.
- Merge the two sorted lists together.

We then split this list into two smaller lists that differ in size by no more than one node. It does not matter which values end up in either list. In the example to follow, list A
will take the first half of the list while list B
will have the second half of the original list.

Next, we recursively sort these two lists.

Finally, we merge these two sorted lists together.

You are encouraged to look over your code for the merge and mergeSort methods from Lesson 25. Reviewing these algorithms as applied to arrays will help you to solve the same mergesort concept with linked lists.
Assignment:
The linked list should be of type java.util.LinkedList
.
The data file to be used in this lab is (file20.txt).
Building the initial linked list from (file20.txt) should follow this logic. As each new piece of data (Id
/Inv
pair) comes off the data file, it is placed at the beginning of the list. Therefore, the first values read from the data file will end up last in the list.
The recursive merge sort algorithm will need the supporting algorithms of splitting and merging lists. List iterators should be used to implement these methods.
Your program should consist of this 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
If your instructor 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 should appear in the MergeList
class. Here are some of the specifications of the MergeList
class.
- The
reverseList
method is stubbed out as a print statement.
- The
split
method is stubbed out as a print statement.
- The
merge
method is stubbed out as a print statement.
- Methods to read the data file and print the list are provided.
Instructions:
Modify and write code as necessary to satisfy the above specifications.
Print out the source for the MergeList
class.
Turn in your source along with the run output.