void merge(int arr[],int l[], int[] r, int left, int right)
    {
        int i = 0, j = 0, k = 0;
        while (i < left && j < right)
        {
            if (l[i] <= r[j]) {
                arr[k++] = l[i++];
            }
            else {
                arr[k++] = r[j++];
            }
        }
        while (j < right) {
            arr[k++] = r[j++];
        }
    }

    public int[] mergeSort(int arr[], int n)
    {
        if (n < 2) return arr;

        int middle = n / 2;

        int[] l = new int[middle];
        int[] r = new int[n - middle];

        for (int i = 0; i < middle; i++)
            l[i] = arr[i];

        for (int i = middle; i < n; i++)
            r[i - middle] = arr[i];

        mergeSort(l, middle);
        mergeSort(r, n - middle);

        merge(arr, l, r, middle, n - middle);

        return arr;
    }