private static void sortList(Integer[] toSortArray) {Integer[] sortedArray = new Integer[toSortArray.length];mergeSortList(toSortArray, sortedArray, 0, toSortArray.length - 1);}private static void mergeSortList(Integer[] toSortArray, Integer[] sortedArray, int low, int high) {if (low >= high)return;int mid = (high + low) / 2;mergeSortList(toSortArray, sortedArray, low, mid);mergeSortList(toSortArray, sortedArray, mid + 1, high);mergeResults(toSortArray, sortedArray, low, mid, high);printArray(toSortArray);}private static void mergeResults(Integer[] toSortArray, Integer[] sortedArray, int low, int mid, int high) {for (int index = low; index <= high; index++) {sortedArray[index] = toSortArray[index];}int leftIndex = low;int rightIndex = mid + 1;for (int k = low; k <= high; k++) {System.out.println(leftIndex + " " + rightIndex + " " + k);if (leftIndex > mid) {toSortArray[k] = sortedArray[rightIndex++];} else if (rightIndex > high) {toSortArray[k] = sortedArray[leftIndex++];} else if (sortedArray[leftIndex] < sortedArray[rightIndex]) {toSortArray[k] = sortedArray[leftIndex++];} else {toSortArray[k] = sortedArray[rightIndex++];}}}
Time Complexity: n log n
No comments:
Post a Comment