UNB/ CS/ David Bremner/ teaching/ java/ MergeList.java
public class MergeList{
    private ComparableNode first,last;
    private int length;
    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 insertFirst(Comparable key) {
        ComparableNode newNode=
            new ComparableNode(key);
        newNode.setNext(first);
        first=newNode;
        if(last == null) {
            last=newNode;
        }
    }
    public void insertLast(Comparable key){
        ComparableNode newNode=
            new ComparableNode(key);
        insertLast(newNode);
    }

    public void insertLast(ComparableNode newNode){
        if (last==null){
            first=newNode;
            last=newNode;
        }  else {
            last.setNext(newNode);
            last=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.first=result.first;
        this.last=result.last;
        this.length=result.length;
    }

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

        if (getLength()<=1)
            return;

        MergeList secondHalf;

        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.print();
        a.insertLast(names[i]);
    }

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

} // class MergeList





//@keywords linked list, week 10, merge