private static int[] merge(int[] left, int[] right) {
        int[] merged = new int[left.length+right.length];
        int leftHead =0; int rightHead = 0;

        for(int i=0; i<left.length+right.length; i++) {

            if(rightHead < right.length && leftHead<left.length &&  left[leftHead]<right[rightHead]) {
                merged[i] = left[leftHead];
                leftHead++;
            } else if(rightHead < right.length && leftHead<left.length && left[leftHead]>right[rightHead]){
                merged[i] = right[rightHead];
                rightHead ++;
            } else if(leftHead>=left.length) {
                merged[i] = right[rightHead];
                rightHead ++;
            } else if(rightHead >= right.length) {
                merged[i] = left[leftHead];
                leftHead++;
            }

        }

        return merged;
    }