package csci151;

import stackproj.adt.Deque;
import stackproj.impl.LinkedListDeque;

public class MergeSort {
    public static Deque<Integer> merge(Deque<Integer> d1, Deque<Integer> d2) {
        Deque result = new LinkedListDeque();
        int l1=d1.getSize();
        int l2=d2.getSize();
        int l=l1+l2;
        for (int i=0; i<l; i++){
            int c1=100000, c2=100000;
            if (d1.getSize()>0) {
                try {
                    c1 = d1.popFromFront();
                } catch (Exception ex) {
                    System.out.println(ex.getMessage());
                }
            }
            if (d2.getSize()>0) {
                try {
                    c2= d2.popFromFront();
                } catch (Exception ex) {
                    System.out.println(ex.getMessage());
                }
            }
            //int n1=0,n2=0;
            if(c1>=c2){
                result.pushToBack(c2);
                d1.pushToFront(c1);
            }else {
                result.pushToBack(c1);
                d2.pushToFront(c2);
            }

        }
        return result;
 /* assuming d1 and d2 are sorted, merge their contents
       into a single sorted Deque, and return it */

    }
    public static void main(String[] args){
        Deque q = new LinkedListDeque();
        Deque c =new LinkedListDeque();
        for (int i=0; i<3; i++){
            q.pushToBack(i); // 0 1 2
        }
        for (int i=2; i<5; i++){
            c.pushToBack(i);//2 3 4
        }

        System.out.println(q);
        System.out.println(c);
        System.out.println(merge(q,c));

    }



    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
     */
     return null;
    }
}