Homework 4A: Merge Sort

Out: November 16, 2001
Due: November 27, 2001

Write a program that implements Merge Sort.

Design Hints

The following are suggestions, and may need to be modified to work, I'm just giving design hints off the top of my head, OK? You will probably need the following Java classes:

• MergeSortTest
• MergeSort
• ReadIntegers
• ReadIntegersException
• LinkedList
• Node

Class MergeSort will have most of the new, interesting code. It will have a recursive method mergeSortAux which:

1. splits the linked list given as argument,
2. calls mergeSortAux on each of the two linked lists,
3. calls mergeLists to glue the two recursively sorted lists together,
4. and returning the newly glued together list as its value.

It seems to me that all methods in MergeSort can be static, and all methods except mergeSort can be private.

MergeSortTest is the class which contains the main method. This method:

1. reads integers from the standard in (a file, by using command line redirection), creating a linked list of integers as it reads,
2. prints this original list,
3. calls mergeSort on the list,
4. and prints the result.

The class ReadIntegers has been provided read integers from standard in. It throws the ReadIntegersException on end of file. An example use of ReadIntegers can be found in the InsertionSortTest code.

A more detailed outline of classes and their methods follows:

class MergeSort
{
   LinkedList splitList(LinkedList listToSplit)
   //  takes listToSplit and creates a new list L.
   //  listToSplit is modified to contain only
   //  half the elements it originally had, the remaining
   //  elements have been added to list L.
   //  The list L is returned as the value of this method. 
   //  If the number of elements on listToSplit is 1,
   //  return null and do not modify listToSplit.


   LinkedList mergeLists(LinkedList l1, LinkedList l2)
   //  merges lists l1 and l2 onto a new list L and returns
   //  L as value of method. LinkedLists l1 and l2 are
   //  modified by a call to this method (they are returned
   //  empty). The "meaning" of the merge is as described
   //  in class: l1 and l2 are linked lists with numbers in
   //  ascending order; the returned list is a list of numbers
   //  in ascending order by merging the elements of l1 and l2.

   LinkedList mergeSortAux(LinkedList ll)
   //  implements merge sort using recursion

   LinkedList mergeSort(LinkedList ll)
   //  calls mergeSortAux on ll after some possible preprocessing
   //  of ll.
}

class MergeSortTest
{
   public static void main(String [] args)
   // inputs integers into a list and calls
   // mergeSort.
}

class LinkedList
{
    void insertAtHead(int numberToInsert)
    //  makes a new node with numberToInsert as the data
    //  in the node and modifies this list to place this
    //  node at the head.

    int removeHead()
    //  removes the node at the head of the list and returns
    //  the data in that node. (Assumes non-empty list)

    int senseHead()
    //  returns the integer value in the data node at the
    //  head of this list. (Assumes non-empty list)

    void insertAtTail(int numberToInsert)
    //  makes a new node with numberToInsert as the data
    //  in the node and modifies this list to palce this
    //  node at the tail.

    boolean isEmpty()
    //  returns true if this list is empty, else returns false.
}

class Node
{
   int data ;
   Node next ;
}

Test suites

The following input files are provided for you to test your code.

• test1
• test2
• test3
• test4

java CreateRandomNumbers > test4.txt