1public class MergeSort {
2
3    public static void mergeSort(int[] arr) {
4        if (arr.length < 2) return;
5        int mid = arr.length / 2;
6        int[] left = new int[mid];
7        int[] right = new int[arr.length - mid];
8
9        // Copy elements from the original array to the left and right subarrays
10        for (int i = 0; i < mid; i++) {
11            left[i] = arr[i];
12        }
13        for (int i = mid; i < arr.length; i++) {
14            right[i - mid] = arr[i];
15        }
16
17        // Recursively sort the left and right subarrays
18        mergeSort(left);
19        mergeSort(right);
20
21        // Merge the sorted subarrays
22        merge(left, right, arr);
23    }
24
25    public static void merge(int[] left, int[] right, int[] arr) {
26        int i = 0, j = 0, k = 0;
27
28        // Merge the two subarrays in sorted order
29        while (i < left.length && j < right.length) {
30            if (left[i] <= right[j]) {
31                arr[k++] = left[i++];
32            } else {
33                arr[k++] = right[j++];
34            }
35        }
36
37        // Copy any remaining elements from the left subarray
38        while (i < left.length) {
39            arr[k++] = left[i++];
40        }
41
42        // Copy any remaining elements from the right subarray
43        while (j < right.length) {
44            arr[k++] = right[j++];
45        }
46    }
47
48    public static void main(String[] args) {
49        int[] arr = {5, 2, 7, 1, 3, 6, 4};
50        mergeSort(arr);
51        for (int num : arr) {
52            System.out.print(num + " ");
53        }
54    }
55
56}