Untitled

mail@pastecode.io avatar
unknown
plain_text
8 months ago
1.4 kB
0
Indexable
Never
public class Main {
	static int[] arr = { 1, 3, 2, 0, 8, 7 };

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		MergeSort s = new MergeSort();

		s.mergeSort(arr, 0, 5);

		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}

	}

}

class MergeSort {
	void mergeSort(int[] arr, int left, int right) {

		if (left < right) {
			int mid = (left + right) / 2;

			mergeSort(arr, left, mid);
			mergeSort(arr, mid + 1, right);

			merge(arr, left, right, mid);
		}
	}

	void merge(int[] arr, int left, int right, int mid) {
		// size of l array, r array
		int n1 = mid - left + 1;
		int n2 = right - mid;

		int[] L = new int[n1];
		int[] R = new int[n2];

		// copy data
		for (int i = 0; i < n1; i++) {
			L[i] = arr[left + i];
		}
		for (int j = 0; j < n2; j++) {
			R[j] = arr[mid + j + 1];
		}
		// merge
		int i = 0;// idx of l array
		int j = 0;// idx of r array
		int k = left; // idx of merge array

		while (i < n1 && j < n2) {
			if (L[i] <= R[j]) {
				arr[k] = L[i];
				i++;
			} else {
				arr[k] = R[j];
				j++;
			}
			k++;
		}
		// copy remaining element of L[]
		while (i < n1) {
			arr[k] = L[i];
			i++;
			k++;
		}
		// copy remaining element of R[]
		while (j < n2) {
			arr[k] = R[j];
			j++;
			k++;
		}

	}

}