src/it/unimi/dsi/fastutil/Arrays.java
private static void inPlaceMerge(final int from, int mid, final int to, final IntComparator comp, final Swapper swapper) {
		if (from >= mid || mid >= to) return;
		if (to - from == 2) {
			if (comp.compare(mid, from) < 0) swapper.swap(from, mid);
			return;
		}

		int firstCut;
		int secondCut;

		if (mid - from > to - mid) {
			firstCut = from + (mid - from) / 2;
			secondCut = lowerBound(mid, to, firstCut, comp);
		}
		else {
			secondCut = mid + (to - mid) / 2;
			firstCut = upperBound(from, mid, secondCut, comp);
		}

		int first2 = firstCut;
		int middle2 = mid;
		int last2 = secondCut;
		if (middle2 != first2 && middle2 != last2) {
			int first1 = first2;
			int last1 = middle2;
			while (first1 < --last1)
				swapper.swap(first1++, last1);
			first1 = middle2;
			last1 = last2;
			while (first1 < --last1)
				swapper.swap(first1++, last1);
			first1 = first2;
			last1 = last2;
			while (first1 < --last1)
				swapper.swap(first1++, last1);
		}

		mid = firstCut + (secondCut - mid);
		inPlaceMerge(from, firstCut, mid, comp, swapper);
		inPlaceMerge(mid, secondCut, to, comp, swapper);
	}
private static void inPlaceMerge(final int from, int mid, final int to, final IntComparator comp, final Swapper swapper) {
		if (from >= mid || mid >= to) return;
		if (to - from == 2) {
			if (comp.compare(mid, from) < 0) swapper.swap(from, mid);
			return;
		}

		int firstCut;
		int secondCut;

		if (mid - from > to - mid) {
			firstCut = from + (mid - from) / 2;
			secondCut = lowerBound(mid, to, firstCut, comp);
		}
		else {
			secondCut = mid + (to - mid) / 2;
			firstCut = upperBound(from, mid, secondCut, comp);
		}

		int first2 = firstCut;
		int middle2 = mid;
		int last2 = secondCut;
		if (middle2 != first2 && middle2 != last2) {
			int first1 = first2;
			int last1 = middle2;
			while (first1 < --last1)
				swapper.swap(first1++, last1);
			first1 = middle2;
			last1 = last2;
			while (first1 < --last1)
				swapper.swap(first1++, last1);
			first1 = first2;
			last1 = last2;
			while (first1 < --last1)
				swapper.swap(first1++, last1);
		}

		mid = firstCut + (secondCut - mid);
		inPlaceMerge(from, firstCut, mid, comp, swapper);
		inPlaceMerge(mid, secondCut, to, comp, swapper);
	}
private static void inPlaceMerge ( final int from , int mid , final int to , final IntComparator comp , final Swapper swapper ) { if ( from >= mid || mid >= to ) return ; if ( to - from == 2 ) { if ( comp . compare ( mid , from ) < 0 ) swapper . swap ( from , mid ) ; return ; } int firstCut ; int secondCut ; if ( mid - from > to - mid ) { firstCut = from + ( mid - from ) / 2 ; secondCut = lowerBound ( mid , to , firstCut , comp ) ; } else { secondCut = mid + ( to - mid ) / 2 ; firstCut = upperBound ( from , mid , secondCut , comp ) ; } int first2 = firstCut ; int middle2 = mid ; int last2 = secondCut ; if ( middle2 != first2 && middle2 != last2 ) { int first1 = first2 ; int last1 = middle2 ; while ( first1 < -- last1 ) swapper . swap ( first1 ++ , last1 ) ; first1 = middle2 ; last1 = last2 ; while ( first1 < -- last1 ) swapper . swap ( first1 ++ , last1 ) ; first1 = first2 ; last1 = last2 ; while ( first1 < -- last1 ) swapper . swap ( first1 ++ , last1 ) ; } mid = firstCut + ( secondCut - mid ) ; inPlaceMerge ( from , firstCut , mid , comp , swapper ) ; inPlaceMerge ( mid , secondCut , to , comp , swapper ) ; }
Transforms two consecutive sorted ranges into a single sorted range. The initial ranges are
{@code [first..middle)} and {@code [middle..last)}, and the resulting range is
{@code [first..last)}. Elements in the first input range will precede equal elements in
the second.
Transforms two consecutive sorted ranges into a single sorted range . The initial ranges are {