Warning: session_start(): open(/var/lib/php/sessions/sess_k0rifhif63qsmojb8niehi40ih, O_RDWR) failed: No space left on device (28) in /var/www/tb-usercake/models/config.php on line 51
Warning: session_start(): Failed to read session data: files (path: /var/lib/php/sessions) in /var/www/tb-usercake/models/config.php on line 51
scope timSortIntArrayWithComparator.
// 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