public class MergeList{
  private ComparableNode first,last;
  private int length;

  // Create an empty list
  public MergeList(){
    this(null,null,0);
  }

  public MergeList(ComparableNode theFirst,
                   ComparableNode theLast,
                   int theLength){
    first=theFirst;
    last=theLast;
    length=theLength;
  }

  public int getLength(){
    return length;
  }

  private void setLength(int len){
    length=len;
  }

  private ComparableNode getFirst(){
    return first;
  }

  private void setFirst(ComparableNode l){
    first=l;
  }

  private ComparableNode getLast(){
    return last;
  }

  private void setLast(ComparableNode l){
    last=l;
  }

  public boolean isEmpty(){
    return (first==null);
  }
  
  public void insertLast(Comparable key){
    ComparableNode newComparableNode=new ComparableNode(key);
    insertLast(newComparableNode);
  }


  public void insertFirst(ComparableNode newNode) {
      
    newNode.setNext(first);
    first=newNode;

    if(last == null) {        
        last=newNode;
    }
  }
  public void insertLast(ComparableNode newNode){
      if (last==null){
          last=newNode;
          first=newNode;
      }  else {
          last=newNode;
          last.setNext(newNode);
      }

      newNode.setNext(null);
      length++;    
  }

  private ComparableNode removeFirst(){
    ComparableNode oldFirst=first;
    first=first.getNext();

    length--;
    return oldFirst;
  }


  /**
     split the list into two halves.
     @param where position of first link of second half.
     @return the second half
     precondition: list has more than 1 element;
  */

  public MergeList split(int where){
    ComparableNode cursor=first;

    for (int i=1; i< where; i++){
      cursor=cursor.getNext();
    }

    MergeList secondHalf=new MergeList(cursor.getNext(), 
                                       last,
                                       length-where);
    last=cursor;
    length=where;
    cursor.setNext(null);

    return secondHalf;
  }


  /**
   Join another list to the end of this one.
   @param other list to join
  */

  public void join(MergeList other){
    length=length+other.length;
    this.last.setNext(other.first);
    this.last=other.last;
  }

  public void print(){
    for (ComparableNode cursor=getFirst(); cursor != null ; 
         cursor=cursor.getNext()){
      System.out.println(cursor.getData());
    }
  }

  private void copy(MergeList other){
    first=other.first;
    last=other.last;
    length=other.length;
  }

  void merge(MergeList other){
      MergeList result=new MergeList();
    while( !(this.isEmpty() || other.isEmpty()) ) {
      
      ComparableNode transfer;

      if (this.getFirst().compareTo(other.getFirst()) <= 0)
        transfer=this.removeFirst();
      else
        transfer=other.removeFirst();

      result.insertLast(transfer);
    }
        
    if (this.getLength()>0){
      result.join(this);
    }

    if (other.getLength()>0){
      result.join(other);
    }

    
    this.copy(result);
  }  


  /**
     Sort the elements of the linked list in place.
     NOTE: this modifies the list.
  */
  public void sort(){

    MergeList secondHalf;

    if (getLength()<=1)
      return;

    secondHalf=this.split(getLength()/2);
    
    this.sort();
    secondHalf.sort();

    this.merge(secondHalf);
  }

  public static void main(String[] args){

    String[] names={"bob","mary","joe","fred"};
    
    MergeList a=new MergeList();

    for (int i=0; i < names.length; i++)
      a.insertLast(names[i]);

    a.sort();
    a.print();
  }

} // class MergeList



    

//