CSCI152 L13 P2

//////////////////////////////////////////////////////////////// Merge Class
public class MergeForDeque {
    public static Deque<Integer> merge(Deque<Integer> d1, Deque<Integer> d2) {
        /* assuming d1 and d2 are sorted, merge their contents
       into a single sorted Deque, and return it */
        int s1=d1.getSize(), s2=d2.getSize();
        Deque<Integer> resD=new LinkedListDeque();
        while (s1>0 || s2>0){
            if (s1>0 && s2>0){
                int x, y;
                try {
                    x=d1.popFromFront();
                    y=d2.popFromFront();
                } catch (Exception ex){
                    x=0;
                    y=0;
                }
                if (x<=y){
                    resD.pushToBack(x);
                    s1--;
                    d1.pushToBack(x);
                    d2.pushToFront(y);
                } else {
                    resD.pushToBack(y);
                    s2--;
                    d2.pushToBack(y);
                    d1.pushToFront(x);
                }
            } else if (s2==0){
                int x;
                try {
                    x=d1.popFromFront();
                } catch (Exception ex){
                    x=0;
                }
                resD.pushToBack(x);
                s1--;
                d1.pushToBack(x);
            } else {
                int y;
                try {
                    y=d2.popFromFront();
                } catch (Exception ex){
                    y=0;
                }
                resD.pushToBack(y);
                s2--;
                d2.pushToBack(y);
            }
        }
        return resD;
    }

    public static Deque<Integer> mergeSort(Deque<Integer> deq) {
        /* Step 0:  base case???
        Step 1:  split deq into two Deques of relatively equal size
        Step 2:  pass both of these Deques into mergeSort
        Step 3:  pass the resulting Deques into merge, and return the result
         */
        int s=deq.getSize(), hs=deq.getSize()/2;
        if (s<=1){
            return deq;
        }
        Deque<Integer> d1=new LinkedListDeque(), d2=new LinkedListDeque();
        while (s>hs){
            int x;
            try{
                x=deq.popFromFront();
            } catch (Exception ex){
                x=0;
            }
            d1.pushToBack(x);
            deq.pushToBack(x);
            s--;
        }
        while (s>0){
            int y;
            try{
                y=deq.popFromFront();
            } catch (Exception ex){
                y=0;
            }
            d2.pushToBack(y);
            deq.pushToBack(y);
            s--;
        }
        d1=mergeSort(d1);
        d2=mergeSort(d2);
        Deque<Integer> resD=merge(d1, d2);
        return resD;
    }
}

///////////////////////////////////////////////////////////// Test Class
public class testClass {

    public static void main(String[] args){
        Deque<Integer> d1=new LinkedListDeque(), d2=new LinkedListDeque();

        for (int i=1; i<=5; i++){
            d1.pushToBack(i);
        }
        System.out.println("Size: "+d1.getSize()+"\n"+d1+"\n");

        for (int i=6; i<=11; i++){
            d2.pushToBack(i);
        }
        System.out.println("Size: "+d2.getSize()+"\n"+d2+"\n");

        Deque<Integer> dm=MergeForDeque.merge(d1, d2);
        System.out.println("Size: "+dm.getSize()+"\n"+dm+"\n");
        System.out.println("Size: "+d1.getSize()+"\n"+d1+"\n");
        System.out.println("Size: "+d2.getSize()+"\n"+d2+"\n");

        d1.clear();
        d1.pushToBack(5);
        d1.pushToBack(1);
        d1.pushToBack(7);
        d1.pushToBack(3);
        d1.pushToBack(1);
        d1.pushToBack(2);
        d1.pushToBack(4);
        d1.pushToBack(6);
        System.out.println("Size: "+d1.getSize()+"\n"+d1+"\n");

        dm=MergeForDeque.mergeSort(d1);
        System.out.println("Size: "+dm.getSize()+"\n"+dm+"\n");
        System.out.println("Size: "+d1.getSize()+"\n"+d1+"\n");
    }
}