public int[] merge(int[] a,int start, int middle,int end){
        int length1 = middle-start+1;
        int length2 = end-middle;
        int[] left = new int[length1+1];
        int[] right = new int[length2+1];
        for (int i = 0; i < left.length-1; i++)
        {
            left[i]=a[start+i];
        }
        left[left.length-1]=Integer.MAX_VALUE;
        for (int i = 0; i < right.length-1; i++)
        {
            right[i]=a[middle+i+1];
        }
        right[right.length-1]=Integer.MAX_VALUE;
        
        int leftIndex=0;
        int rightIndex=0;
        for (int i = start; i < end+1; i++)
        {
            
            if (left[leftIndex]<=right[rightIndex])
            {
                if(left[leftIndex]!=Integer.MAX_VALUE){
                    a[i]=left[leftIndex];
                    leftIndex++;
                }
                
            }else {
                if(right[rightIndex]!=Integer.MAX_VALUE){
                    a[i]=right[rightIndex];
                    rightIndex++;
                }
                
            }
            
        }
        return a;
    }