CS 206 - Introduction to Data Structures

Assignment 10: Due 11:59PM Thursday April 23, 11:59pm

Implement Merge sort on Linked Lists

Look in MergeLL. That file contains everything you need to implement merge sort on a doubly linked list. Indeed it builds doubly linked lists for you.

The basic algorithm for merge sort on linked lists is more or less identical to the algorithm for merge sort on arrays. Namely, split the list into two parts, keep doing that recursively until the parts are of size 1 (or 0). Then merge the parts back together. Sounds simple, yes?

Extra credit (and only a small amount of extra credit) Merge sort can be done more efficently on linked lists by doing somthing akin to the "bottom up" construction of heaps. (See section 9.3.4 of textbook.) The basic idea is to take a pass throught the list doing 2-wise merging. The another pass doing 4-wise merging. Then 8-wise, until you attempt a pass longer than the list. You can do this purely using iteration. Only do this if you are confident that your merge sort using the basic implementation works. (This implemetation can be tricky. Realistically, it is impractical without a doubly linked list.)

• To split a list in half, first find the node in the middle. Then do something like:

  			// Node middleNode;  // This was found somehow else.
  			Node headOfSecondHalf = middleNode.next;
  			middleNode.next = null;
  			headOfSecondHalf.prev=null;
  		

• Once the list is created, do not create any new nodes. Do everything by adjustiung the "next" and "prev" pointers. (As in the list splitter above). The only place new nodes should be created is in the provided push method.
• Be careful to keep you merge sort an O(n * log2(n)) algorithm. Some mistakes could result in a runtime of O(n*n) or worse.
• Depending on how you use recursion you may not be able to sort big lists (more than 1,000,000) nodes. That is OK, not good, but OK.
• This assignment should require writing less than 100 lines of code (not including comments). If you are doing the extra credit you will need (probably) more than 100 lines of code.
• An implementation that copies the linked list into an array, sorts the array, then recreates the linked list will not be accepted!
• You may use any combination of iteration and recursion that pleases you.
• You man not use any auxiliary data structures. (This also goes to outlawing the copy into an array ... )
• The main function of MergeLL in the submitted code should be exactly what it is in the provided code. Namely

  	public static void main(String[] args) 
      { 
          MergeLL li = new MergeLL(); 
          li.dotest(1, 30, true);
          li.dotest(7, 4000000, false);
      }
  		

• Unless you make it clear, I will assume that all of your code is in the file MergeLL.java

A (small) portion of your grade will be based upon the speed of your implementation. My Linked List implementation of merge sort is considerably slower than the array mergesort. (It is slower than heapsort.) Do not compare times on your machine to the times I have published. Generate times for you own machine and compare those.

Electronic Submissions

• README: This file should follow the format of this sample README (https://cs.brynmawr.edu/cs206/README.txt)
  • Within the README file, include a brief (max 1 paragraph) reflection on what went well and/or poorly and why
• Source files: Every .java file used in the final version of every part of your project (including the imported files)
• Unique Data files used: If any (you might have a leaf image?)

The following steps for submission assume you are using Eclipse, and that you created a project named AssignmentN in the directory /home/YOU/cs206/

1. For this assignment N=10
2. Put the README file into the project directory
3. Go to the directory /home/YOU/cs206
4. Enter submit -c 206 -p N -d AssignmentN