public class MyMergeSort {
private int [] data;

public MyMergeSort(int[] data){
    this.data = data;
}

public int[] sort(int[] data){
    if (data.length < 2){
        return data;
    }
    int mid = data.length/2;
    int first[] = new int[mid];
    int second[] = new int[data.length - mid];
    System.arraycopy(data, 0, first, 0, mid);
    System.arraycopy(data, mid, second, 0, data.length - mid);
    return merge(sort(first), sort(second));
}

private int[] merge(int[] arr1, int[] arr2) {
    if(arr1.length == 0){
        return arr2;
    }
    if(arr2.length == 0){
        return arr1;
    }
    int res[] = new int[arr1.length + arr2.length];
    int i;
    int j = 0; // iterate over the first array
    int k  = 0; // iterate over the second array
    for (i = 0; i < res.length; i++) {
        if(j < arr1.length && k < arr2.length){
            if(arr1[j] < arr2[k]){
                res[i] = arr1[j];
                j++;
            }
            else{
                res[i] = arr2[k];
                k++;
            }
        }
        else{
            if(j < arr1.length){
                System.arraycopy(arr1, j, res, i, arr1.length-j);
                break;
            }
            else{
                System.arraycopy(arr2, k, res, i, arr2.length-k);
                break;
            }
        }
    }
    return res;
}

public static void main(String[] args) {
    int d[] = {1, 9, 2, 8, 6, 3, 7, 4, 2};
    MyMergeSort mySort = new MyMergeSort(d);
    int res[] = new int[d.length];
    res =  mySort.sort(d);
    for (int i = 0; i < res.length; i++) {
        System.out.print(res[i] + " ");
    }
}

}

public class MyMergeSort {
    private int [] data;
    
    public MyMergeSort(int[] data){
        this.data = data;
    }
    
    public int[] sort(int[] data){
        if (data.length < 2){
            return data;
        }
        int mid = data.length/2;
        int first[] = new int[mid];
        int second[] = new int[data.length - mid];
        System.arraycopy(data, 0, first, 0, mid);
        System.arraycopy(data, mid, second, 0, data.length - mid);
        return merge(sort(first), sort(second));
    }

    private int[] merge(int[] arr1, int[] arr2) {
        if(arr1.length == 0){
            return arr2;
        }
        if(arr2.length == 0){
            return arr1;
        }
        int res[] = new int[arr1.length + arr2.length];
        int i;
        int j = 0; // iterate over the first array
        int k  = 0; // iterate over the second array
        for (i = 0; i < res.length; i++) {
            if(j < arr1.length && k < arr2.length){
                if(arr1[j] < arr2[k]){
                    res[i] = arr1[j];
                    j++;
                }
                else{
                    res[i] = arr2[k];
                    k++;
                }
            }
            else{
                if(j < arr1.length){
                    System.arraycopy(arr1, j, res, i, arr1.length-j);
                    break;
                }
                else{
                    System.arraycopy(arr2, k, res, i, arr2.length-k);
                    break;
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int d[] = {1, 9, 2, 8, 6, 3, 7, 4, 2};
        MyMergeSort mySort = new MyMergeSort(d);
        int res[] = new int[d.length];
        res =  mySort.sort(d);
        for (int i = 0; i < res.length; i++) {
            System.out.print(res[i] + " ");
        }
    }
}