public class _5 {
    public static void main(String[] args) {
        int arr[] = {6, 2, 1, 5, 7, 8, 0, 9};
        int low = 0;
        int high = arr.length - 1;

        ms(arr, low, high);

        for (int e : arr) {
            System.out.print(e + " ");
        }
    }

    static void ms(int arr[], int low, int high) {
        if (low < high) {
            int mid = (low + high) / 2;
            ms(arr, low, mid);       // Sort left half
            ms(arr, mid + 1, high); // Sort right half
            merge(arr, low, mid, high);
        }
    }

    static void merge(int arr[], int low, int mid, int high) {
        int[] arr2 = new int[arr.length]; // Temporary array for merging
        int i = low;      // Starting index for left subarray
        int j = mid + 1;  // Starting index for right subarray
        int k = low;      // Starting index to store merged values

        // Merge the two subarrays into arr2
        while (i <= mid && j <= high) {
            if (arr[i] < arr[j]) {
                arr2[k] = arr[i];
                i++;
            } else {
                arr2[k] = arr[j];
                j++;
            }
            k++;
        }

        // Copy remaining elements of left subarray, if any
        while (i <= mid) {
            arr2[k] = arr[i];
            i++;
            k++;
        }

        // Copy remaining elements of right subarray, if any
        while (j <= high) {
            arr2[k] = arr[j];
            j++;
            k++;
        }

        // Copy merged elements back to the original array
        for (int x = low; x <= high; x++) {
            arr[x] = arr2[x];
        }
    }
}