public static void merge(Comparable[] a1, int left1, int right1, Comparable[] a2, int left2, int right2, Comparable[] a,int left) {
    // Merge a1[left1...right1] and a2[left2...right2] into
        // a[left...] (where both a1 and a2 are sorted).
        int i = left1, j = left2, k = left;
        while (i <= right1 && j <= right2) {
        //both a1 and a2 contain elements to be merged
            int comp = a1[i].compareTo(a2[j]);
            if (comp <= 0) {
        //a1 contains the smallest element, so it is copied //into the output array a
            a[k++] = a1[i++];
            }
            else {
        //a2 contains the smallest element, so it is copied
        //into the output array a
                a[k++] = a2[j++];
            }
        }
        while (i <= right1) {
        // All elements in a2 have been sorted
        //Copy the remainder elements from a1
           a[k++] = a1[i++];
        }
        while (j <= right2) {
        // All elements in a1 have been sorted
        //Copy the remainder elements from a2
            a[k++] = a2[j++];
        }
    }

    public void merge_sort(int left, int right) {
        //Declare m
        int m;

        //If left < right
        if (left < right) {
            //1.1 Let m be about midway between left and right.
            m = (left + right) / 2;
            //RECURSIVE PART//
            //1.2 Sort a[left..m] into ascending order.
            merge_sort(left, m);
            //1.3 Sort a[m+1...right]
            merge_sort(m + 1, right);
            //1.4 Merge a[left..m] and a[m+1...right] into an auxiliary array
            merge(left, m, right);
        }
    }