The Merge Sort Algorithm

The merge sort algorithm is pretty fast algorithm for sorting list elements. Its running time is O(n log n). The merge sort may implement a recursive approach. Splitting sets the data to the stage where it is eligible for being merge.

public class MergeSort {
	public static void sort(int inputArray[]) {
		sort(inputArray, 0, inputArray.length-1);
	}
	
	public static void sort(int inputArray[], int start, int end) {
		if (end <= start) {
			return; // done traversing the array
		}
		int mid = (start + end) / 2;
		sort(inputArray, start, mid); // sort left half
		sort(inputArray, mid+1, end); // sort right half
		merge(inputArray, start, mid, end);
	}
	
	public static void merge(int inputArray[], int start, int mid, int end) {
		int[] tempArray = new int[end - start + 1];
		int leftSlot = start;
		int rightSlot = mid + 1;
		int k = 0;
		
		while(leftSlot <= mid && rightSlot <= end) {
			if (inputArray[leftSlot] < inputArray[rightSlot]) {
				tempArray[k] = inputArray[leftSlot];
				leftSlot++;
			} else {
				tempArray[k] = inputArray[rightSlot];
				rightSlot++;
			}
			k++;
		}
		
		if (leftSlot <= mid) {
			while(leftSlot <= mid) {
				tempArray[k] = inputArray[leftSlot];
				leftSlot++;
				k++;
			}
		} else if (rightSlot <= end) {
			while(rightSlot <= end) {
				tempArray[k] = inputArray[rightSlot];
				rightSlot++;
				k++;
			}
		}
		
		for (int i = 0; i < tempArray.length; i++) {
			inputArray[start+i] = tempArray[i];
		}
		
	}
}

Starting point:

int[] inputArray = {9,8,3,13,87,12,99};
MergeSort sorter = new MergeSort();
		
sorter.sort(inputArray);
for (int i = 0; i < inputArray.length; i++) {
    System.out.print(inputArray[i] + " ");
}