public class ListWithMerge<E extends Comparable<? super E>> implements 
				ListInterface<E>{

    private Node<E> head; 

    private int numItems;  

    public ListWithMerge(){ 
	numItems = 0;
	head = null;
    }

    public boolean isEmpty(){
	return (head==null);
    }

    public int size(){
	return numItems;
    }

    public void add (int index, E item){
	if (index==0){ 
	    Node<E> newNode = new Node(item,head);
	    head = newNode;
	}
	else{ 
	    Node<E> prev = find(index-1);
	    Node<E> newNode = new Node<E>(item,prev.getNext());	   
	    prev.setNext(newNode);
	}
	numItems++;
    }

    private Node<E> find (int index){
	Node<E> curr = head;
	for (int i=0; i<index; i++)
	    curr = curr.getNext();
	return curr;
    }

    public E get (int index){
	Node<E> curr = find (index);
	return curr.getItem();
    }

    public void remove (int index){
	if (index==0)
	    head = head.getNext();
	else{
	    Node<E> prev = find (index-1);
	    Node<E> curr = prev.getNext();
	    prev.setNext(curr.getNext());
	}
	numItems--;
    }

    public void removeAll(){
	head = null;
	numItems = 0;
    }

    public void mergesort(){
	if (size() > 1){
	    ListWithMerge<E> secondHalf = splitList();
	    this.mergesort();
	    secondHalf.mergesort();
	    merge (secondHalf);
	}
    }

    private ListWithMerge<E> splitList(){
	ListWithMerge<E> ret = new ListWithMerge<E>();
	int newLast = (size() - 1)/2;
	Node<E> lastOfFirstHalf = this.find(newLast);
	ret.head = lastOfFirstHalf.getNext();
	ret.numItems = size() - newLast - 1;
	lastOfFirstHalf.setNext(null);
	this.numItems = newLast + 1;
	return ret;
    }

    private void merge (ListWithMerge<E> secondList){
	Node<E> curr1 = this.head;
	Node<E> curr2 = secondList.head;
	Node<E> prev;
	int newSize = this.size() + secondList.size();

	// assumes that neither curr1 nor curr2 is empty:
	// this is always valid when calling merge from mergesort

	if (curr1.getItem().compareTo(curr2.getItem()) > 0){
	    this.head = curr2;
	    prev = curr2;
	    curr2 = curr2.getNext();
	}
	else{
	    prev = curr1; 
	    curr1 = curr1.getNext();
	}

	while (curr1 != null && curr2 != null){
	    if (curr1.getItem().compareTo(curr2.getItem()) > 0){
		prev.setNext(curr2);
		prev = curr2;
		curr2 = curr2.getNext();
	    } // end if
	    else{
		prev.setNext(curr1);
		prev = curr1;
		curr1 = curr1.getNext();
	    } // end else
	} // end while

	if (curr1 != null)
	    prev.setNext(curr1);
	else
	    prev.setNext(curr2);

	numItems = newSize;

	// update secondList to be empty:
	secondList.head = null;
	secondList.numItems = 0;

    } // end merge

} // end ListWithMerge