CS 206 - Introduction to Data Structures

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

Implement Merge sort on Linked Lists

Get the two files SortBase.java and MergeLL.java into VSC. (The files are also available in /home/gtowell/Public206/a10. )

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.)

Some hints, thoughts, and requirements:

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

Your program will be graded based on how it runs on the department’s Linux server, not how it runs on your computer. The submission should include the following items: DO NOT INCLUDE:
Data files that are read from the class site.

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

For more on using the submit script click here