Untitled

mail@pastecode.io avatar
unknown
plain_text
3 years ago
1.2 kB
2
Indexable
Never
import java.util.*;
public class MergeSort 
{
	static void merge(int arr[], int l, int m, int r)
	{
		int n1 = m - l + 1;
		int n2 = r - m;

		int left[] = new int[n1];
		int right[] = new int[n2];

		for (int i = 0; i < n1; ++i)
			left[i] = arr[l + i];
		for (int j = 0; j < n2; ++j)
			right[j] = arr[m + 1 + j];
	int i = 0, j = 0;

		int k = l;
		while (i < n1 && j < n2) {
			if (left[i] <= right[j]) {
				arr[k++] = left[i++];
			}
			else 
				arr[k++] = right[j++];
		}

		while (i < n1) {
			arr[k++] = left[i++];
		}

		while (j < n2) {
			arr[k++] = right[j++];
		}
	}
	static void sort(int arr[], int l, int r)
	{
		if (l < r) {
			int m = (l + r) / 2;
         sort(arr, l, m);
			sort(arr, m + 1, r);

		merge(arr, l, m, r);
		}
	}

	public static void main(String args[])
	{
	    Scanner s=new Scanner(System.in);
	    System.out.println("Enter the size");
		int n=s.nextInt();
	    System.out.println("Enter the array elements");
		int a[]=new int[n];
		for(int i=0;i<n;i++)
		a[i]=s.nextInt();
		sort(a,0,n-1);

		System.out.println("Sorted array");
	System.out.println(Arrays.toString(a));	
	}
}