scope timSortIntArrayWithComparator. // not actually Timsort, but works well // This code has been contributed by 29AjayKumar // from: https://www.geeksforgeeks.org/timsort/ static final int #RUN = 32; // this function sorts array from left index to // to right index which is of size atmost RUN svoid #insertionSort(int[] arr, IntComparator comparator, int left, int right) { for (int i = left + 1; i <= right; i++) { int temp = arr[i]; int j = i - 1; while (j >= left && comparator.compare(arr[j], temp) > 0) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = temp; } } // merge function merges the sorted runs svoid #merge(int[] arr, IntComparator comparator, int l, int m, int r) { // original array is broken in two parts // left and right array int len1 = m - l + 1, len2 = r - m; int[] left = new int[len1]; int[] right = new int[len2]; for (int x = 0; x < len1; x++) { left[x] = arr[l + x]; } for (int x = 0; x < len2; x++) { right[x] = arr[m + 1 + x]; } int i = 0; int j = 0; int k = l; // after comparing, we merge those two array // in larger sub array while (i < len1 && j < len2) { if (comparator.compare(left[i], right[j]) <= 0) { arr[k] = left[i]; i++; } else { arr[k] = right[j]; j++; } k++; } // copy remaining elements of left, if any while (i < len1) { arr[k] = left[i]; k++; i++; } // copy remaining element of right, if any while (j < len2) { arr[k] = right[j]; k++; j++; } } // iterative Timsort function to sort the // array[0...n-1] (similar to merge sort) svoid timSortIntArrayWithComparator(int[] arr, int n default lIntArray(arr), IntComparator comparator) { // Sort individual subarrays of size RUN for (int i = 0; i < n; i += RUN) { insertionSort(arr, comparator, i, Math.min((i + 31), (n - 1))); } // start merging from size RUN (or 32). It will merge // to form size 64, then 128, 256 and so on .... for (int size = RUN; size < n; size = 2 * size) { ifdef timSort_debug print("size=" + size); endifdef // pick starting point of left sub array. We // are going to merge arr[left..left+size-1] // and arr[left+size, left+2*size-1] // After every merge, we increase left by 2*size for (int left = 0; left < n; left += 2 * size) { // find ending point of left sub array // mid+1 is starting point of right sub array int mid = Math.min(left + size - 1, n - 1); int right = Math.min(left + 2 * size - 1, n - 1); // merge sub array arr[left.....mid] & // arr[mid+1....right] merge(arr, comparator, left, mid, right); } } } end scope