package Sorting; public class MergeSort { //this is to address the question on Page 39 in CLRS 2nd edition private static int inversionCounts = 0; public static void mergeSort(int[] array) { int length = array.length; int[] temp = new int[length]; sort(array, 0, length - 1, temp); } private static void sort(int[] array, int i, int j, int[] temp) { if (i >= j) return; int mid = (i + j) / 2; sort(array, i, mid, temp); sort(array, mid + 1, j, temp); merge(array, i, mid, j, temp); } private static void merge(int[] array, int i, int k, int j, int[] temp) { int left = i, right = k + 1, index = i; while(left <= k && right <= j) { if (array[left] < array[right]) { temp[index++] = array[left++]; } else { temp[index++] = array[right++]; inversionCounts += (k - left + 1); } } while(left <= k) { temp[index++] = array[left++]; } while(right <= j) { temp[index++] = array[right++]; } for (index = i; index <= j; index++) { array[index] = temp[index]; } } public static void main(String[] args) { int[] numbers = {8, 6, 3, 2, 1}; for (int n : numbers) { System.out.print(n + " "); } mergeSort(numbers); System.out.println(); for (int n : numbers) { System.out.print(n + " "); } System.out.println(); System.out.println(inversionCounts); } }