public class MergeSort {
	private final int[] arr;

	public MergeSort(int[] arr) {
		this.arr = arr;
	}

	public int[] sort() {
		int start = 0;
		int end = arr.length - 1;

		mergeSort(start, end);

		return arr;
	}

	private void mergeSort(int start, int end) {
		if (start < end) {                              // Return if start == end
			int mid = (start + end) / 2;                // Find the mid

			mergeSort(start, mid);                      // Do recursion with left side variables
			mergeSort(mid + 1, end);                    // Do recursion with right side variables

			merge(start, mid, end);                     // When both of the recursion return the merge left and right variables
		}
	}

	private void merge(int start, int mid, int end) {
		int m = (mid - start) + 1;      // Size of the first array
		int n = (end - mid);

		int[] arr1 = new int[m];        // Create the first array
		int[] arr2 = new int[n];        // Create the second array

		int i, j, k = start;

		// Copy m number of variables starting from main array starting from index start to first array
		for (i = 0; i < m; i++) {
			arr1[i] = arr[k++];
		}

		// Copy n number of variables starting from main array staring from mid + 1 to the second array
		for (j = 0; j < n; j++) {
			arr2[j] = arr[k++];
		}

		i = j = 0;
		k = start;

		// Break through the while when either i become m or j becomes n
		while (i != m && j != n) {
            /*
                Basically it's just one kinda sort
                - if element from the first array is less than the element from the second array then that element should be inserted in the main array
                - otherwise element from the second array should be entered to the main array
             */
			if (arr1[i] < arr2[j]) {
				arr[k++] = arr1[i++];
			} else {
				arr[k++] = arr2[j++];
			}
		}

		// If any elements remaining in the first array then those should also be inserted in the main array
		while (i != m) {
			arr[k++] = arr1[i++];
		}

		// If any elements remaining in the second array then those should also be inserted in the main array
		while (j != n) {
			arr[k++] = arr2[j++];
		}
	}
}