ALGORITHMO #17 - Merge Sort Implementation.java

ALGORITHMO-17-Merge-Sort-Implementation.java

public class MergeSort {
	
	public static int[] mergeSort(int[] arr) { // Note that arr[] will play the role of C[]
		if (arr.length > 1) {
			int m = arr.length / 2;
			int n = arr.length - m;
			
			int[] A = new int[m];
			int[] B = new int[n];
			
			// Fill A[]
			for (int p = 0; p < m; ++p) {
				A[p] = arr[p];
			}
			
			// Fill B[]
			int q = 0;
			for (int p = m; p < arr.length; ++p) {
				B[q] = arr[p];
				q++;
			}
			
			// Recursively split and sort both sub-arrays
			A = mergeSort(A);
			B = mergeSort(B);
			
			// Merge sub-arrays
			int i = 0;
			int j = 0;
			int k = 0;
			
			while (i < m && j < n) {
				if (A[i] <= B[j]) {
					arr[k] = A[i];
					k++;
					i++;
				}
				else {
					arr[k] = B[j];
					k++;
					j++;
				}
			}
			
			if (i < m) {
				// Add the rest of A[]'s elements to arr[]
				for (int p = i; p < m; ++p) {
					arr[k] = A[p];
					k++;
				}
			}
			else {
				// Add the rest of B[]'s elements to arr[]
				for (int p = j; p < n; ++p) {
					arr[k] = B[p];
					k++;
				}
			}
		}
		
		return arr;
	}
	
	public static void main(String[] args) {
		int[] arr = new int[] { 14, 33, 27, 10, 35, 19, 42, 44 };
		
		arr = mergeSort(arr);
		
		for (int element : arr) {
			System.out.print(element + " ");
		}
	}
	
}