Merge Sort

import java.util.*;
import java.io.*;

class Solution {

	static void merge(int[] arr, int l, int mid, int r) {

		int n1 = mid - l + 1;
		int n2 = r - mid;

		// Copy of the array

		int[] arr1 = new int[n1];
		int[] arr2 = new int[n2];

		// 1st array range is : [l---mid]

		int index = 0;
		for (int i = l; i <= mid; i++) {
			arr1[index] = arr[i];
			index++;
		}

		index = 0;
		for (int i = mid + 1; i <= r; i++) {
			arr2[index] = arr[i];
			index++;
		}

		// Same merge Logic

		int index1 = 0;
		int index2 = 0;

		int ansIndex = l;

		while (index1 < n1 && index2 < n2) { // Util there are values in both array

			if (arr1[index1] < arr2[index2]) {
				arr[ansIndex] = arr1[index1];
				index1++;
			} else {
				arr[ansIndex] = arr2[index2];
				index2++;
			}
			ansIndex++;
		} // This while loop will run until there are element of the arrays

		// Copying the elements of the reaming array into my ansArray

		while (index1 < n1) {
			arr[ansIndex++] = arr1[index1++];
		}

		while (index2 < n2) {
			arr[ansIndex++] = arr2[index2++];
		}

		return;

	}

	public void mergeSort(int[] arr, int l, int r) {

		if (r == l) { // 1 element case
			return;
		}

		int mid = (l + r) / 2;

		mergeSort(arr, l, mid);
		mergeSort(arr, mid + 1, r);

		// mergeSort function would have sorted the array
		// 1st array (l,mid) has been sorted
		// 2nd array (mid+1,r) has also been sorted

		merge(arr, l, mid, r);

	}

}

public class Main {
	public static void main(String args[]) {
		Scanner input = new Scanner(System.in);
		int n = input.nextInt();
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = input.nextInt();
		Solution Obj = new Solution();
		Obj.mergeSort(a, 0, n - 1);
		for (int i = 0; i < n; i++)
			System.out.print(a[i] + " ");
	}
}