MergeSort in Java

MergeSort.java

import java.util.Arrays;
import java.util.Scanner;

class MergeSort {
	private static Scanner sc;

	public static void main(String args[]) {
		sc = new Scanner(System.in);

		System.out.println("Enter no of terms");
		int n = sc.nextInt();

		System.out.println("Enter the terms");
		int arr[] = new int[n];
		for (int i = 0; i < n; i++)
			arr[i] = sc.nextInt();

		System.out.println("The unsorted array is:");
		System.out.println(Arrays.toString(arr));

		mergesort(arr);

		System.out.println("The sorted array is:");
		System.out.println(Arrays.toString(arr));
	}

	static void mergesort(int arr[]) {
		int n = arr.length;
		if (n < 2)
			return;
		int mid = n / 2;
		int left[] = new int[mid];
		int right[] = new int[n - mid];
		for (int i = 0; i < mid; i++)
			left[i] = arr[i];
		for (int i = mid; i < n; i++)
			right[i - mid] = arr[i];
		mergesort(left);
		mergesort(right);
		merge(arr, left, right);
	}

	public static void merge(int arr[], int left[], int right[]) {
		int nL = left.length;
		int nR = right.length;
		int i = 0, j = 0, k = 0;
		while (i < nL && j < nR) {
			if (left[i] <= right[j]) {
				arr[k] = left[i];
				i++;
			} else {
				arr[k] = right[j];
				j++;
			}
			k++;
		}
		while (i < nL) {
			arr[k] = left[i];
			i++;
			k++;
		}
		while (j < nR) {
			arr[k] = right[j];
			j++;
			k++;
		}
	}
}

Thanks for this

Thank you for code.

It doesn't work with this array {7, 3, 4, 5, 1, 10, 2, 8, 6, 9}.

Thanks a lot this is very good way of coding.
There is a small correction on line number 52...... arr[k] = right[i]; --> should be arr[k] = right[j];

There is a bug here arr[k] = right[i] it should be right[j]

If you are visiting this page in 2021, here's the code!

private static void mergeSort(int[] nums) {
        if (nums.length < 2)
            return;
        int mid = nums.length / 2;

        int[] left = Arrays.copyOfRange(nums, 0, mid);
        mergeSort(left);
        int[] right = Arrays.copyOfRange(nums, mid, nums.length);
        mergeSort(right);

        // Merge the two arrays
        merge(nums, left, right);
    }

    private static void merge(int[] nums, int[] left, int[] right) {
        int pL = 0, pR = 0, index = 0;
        while (pL < left.length && pR < right.length) {
            if (left[pL] < right[pR]) {
                nums[index++] = left[pL++];
            } else {
                nums[index++] = right[pR++];
            }
        }
        while (pL < left.length) {
            nums[index++] = left[pL++];
        }
        while (pR < right.length) {
            nums[index++] = right[pR++];
        }
    }

Thanks man your code is simple and readable.