import java.util.Arrays;
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; // array travels seems done
}
int mid = (start + end) / 2;
sort(inputArray, start, mid);
sort(inputArray, mid+1,end);
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 leftCounter = start;
int rightCounter = mid+1;
int tempArrayCounter=0;
while(leftCounter <=mid && rightCounter<=end) {
if(inputArray[leftCounter] < inputArray[rightCounter]) {
tempArray[tempArrayCounter]=inputArray[leftCounter];
leftCounter++;
}else {
tempArray[tempArrayCounter]=inputArray[rightCounter];
rightCounter++;
}
tempArrayCounter++;
}
// left and right should have been sorted by now
if(leftCounter <= mid) {
while(leftCounter <= mid) {
tempArray[tempArrayCounter] = inputArray[leftCounter];
leftCounter++;
tempArrayCounter++;
}
} else if(rightCounter <= end) {
while(rightCounter <= end) {
tempArray[tempArrayCounter]= inputArray[rightCounter];
rightCounter++;
tempArrayCounter++;
}
}
// copy temp array to input array
for(int i =0;i<tempArray.length;i++) {
inputArray[start+i] = tempArray[i];
}
}
public static void main(String[] args) {
int[] inputArray = {9,7,3,10,1,8,4,6};
sort(inputArray);
System.out.println(Arrays.toString(inputArray));
}
}
Output:
[1, 3, 4, 6, 7, 8, 9, 10]