public class MergeList<T extends Comparable<T>>{
    private ComparableNode<T> first,last;
    private int length;
    public MergeList(){
        this(null,null,0);
    }
    public MergeList(ComparableNode<T> theFirst,
                     ComparableNode<T> theLast,
                     int theLength){
        first=theFirst;
        last=theLast;
        length=theLength;
    }
    public int getLength(){
        return length;
    }

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

    private ComparableNode<T> getFirst(){
        return first;
    }

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

    private ComparableNode<T> getLast(){
        return last;
    }

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

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

    public void insertFirst(T key) {
        ComparableNode<T> newNode=
            new ComparableNode<T>(key);
        newNode.setNext(first);
        first=newNode;
        length++;
        if(last == null) {
            last=newNode;
        }
    }
    public void insertLast(T key){
        ComparableNode<T> newNode=
            new ComparableNode<T>(key);
        insertLast(newNode);
    }
    public void insertLast(ComparableNode<T> newNode){
        if (last==null){
            first=newNode;
            last=newNode;
        }  else {
            last.setNext(newNode);
            last=newNode;
        }
        newNode.setNext(null);
        length++;
    }
    private ComparableNode<T> removeFirst(){
        ComparableNode<T> 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<T> split(int where){
        ComparableNode<T> cursor=first;
        for (int i=1; i< where; i++){
            cursor=cursor.getNext();
        }
        MergeList<T> 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<T> other){
        length=length+other.length;
        this.last.setNext(other.first);
        this.last=other.last;
    }

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

    private void copy(MergeList<T> other){
        first=other.first;
        last=other.last;
        length=other.length;
    }

    void merge(MergeList<T> other){
        MergeList<T> result=new MergeList<T>();
        while(!(this.isEmpty()||other.isEmpty())){
            ComparableNode<T> 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<T> 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",
                        "dancer", "prancer", "rudolph",
                        "santa"};

        MergeList<String> a=new MergeList<>();

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

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

} // class MergeList





//@keywords linked list, week 10, merge