import java.util.Scanner; public class MergeSort { // ---------- Merge Function ---------- public static void merge(int[] arr, int left, int mid, int right) { int i = left; int j = mid + 1; int k = 0; int[] temp = new int[right - left + 1]; // Merge two sorted halves while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } // Copy remaining elements while (i <= mid) { temp[k++] = arr[i++]; } while (j <= right) { temp[k++] = arr[j++]; } // Copy temp back into original array for (i = left, k = 0; i <= right; i++, k++) { arr[i] = temp[k]; } } // ---------- Merge Sort Function ---------- public static void mergeSort(int[] arr, int left, int right) { if (left < right) { int mid = (left + right) / 2; mergeSort(arr, left, mid); // Sort left half mergeSort(arr, mid + 1, right); // Sort right half merge(arr, left, mid, right); // Merge two halves } } // ---------- Main Method ---------- public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.print("Enter size of array: "); int n = sc.nextInt(); int[] arr = new int[n]; System.out.println("Enter " + n + " elements:"); for (int i = 0; i < n; i++) { arr[i] = sc.nextInt(); } mergeSort(arr, 0, n - 1); System.out.println("Sorted Array:"); for (int x : arr) { System.out.print(x + " "); } sc.close(); } }