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]