Insertionsort for small size groups
771220
private void ssInsertionSort(int PA, int first, int last, int depth) {
        // PA, first, last are pointers in SA
        int i, j;// pointers in SA
        int t, r;

        for (i = last - 2; first <= i; --i) {
            for (t = SA[i], j = i + 1; 0 < (r = ssCompare(PA + t, PA + SA[j], depth)); ) {
                do {
                    SA[j - 1] = SA[j];
                }
                while ((++j < last) && (SA[j] < 0));
                if (last <= j) {
                    break;
                }
            }
            if (r == 0) {
                SA[j] = ~SA[j];
            }
            SA[j - 1] = t;
        }

    }
606109
private void sort(final T[] array, int start, int end, Comparator<T> lt) {
    if (start == end)
      return;
    if ((end - start) <= 15)
      this.selectionSort(array, start, end, lt);
    else {
      final T pivot = array[start + ((end - start) / 2)];
      T tmp;
      int i = start - 1;
      int j = end;
      while (true) {
        do
          i++;
        while (lt.compare(array[i], pivot) < 0);
        do
          j--;
        while (lt.compare(pivot, array[j]) < 0);
        if (i >= j)
          break;
        tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
      }
      this.sort(array, start, i, lt);
      this.sort(array, i, end, lt);
    }
  }
658402
private static void sort1(Quicksortable q, int off, int k, int len) {
        // we don't care about anything >= to k
        if (off >= k)
            return;
        // Insertion sort on smallest arrays
        if (len < 7) {
            for (int i = off; i < len + off; i++)
                for (int j = i; j > off && q.compare(j, j - 1) < 0; j--)
                    q.swap(j, j - 1);
            return;
        }

        // Choose a partition element, v
        int m = off + (len >> 1);       // Small arrays, middle element
        if (len > 7) {
            int l = off;
            int n = off + len - 1;
            if (len > 40) {        // Big arrays, pseudomedian of 9
                int s = len / 8;
                l = med3(q, l, l + s, l + 2 * s);
                m = med3(q, m - s, m, m + s);
                n = med3(q, n - 2 * s, n - s, n);
            }
            m = med3(q, l, m, n); // Mid-size, med of 3
        }
        // move the pivot element to to the front
        q.swap(off, m);
        m = off;

        // Establish Invariant: m* (<m)* (>m)* m*
        int a = off+1, b = a, c = off + len - 1, d = c;
        int cmp;
        while (true) {
            while (b <= c && (cmp = q.compare(b, off)) <= 0) {
                if (cmp == 0)
                    q.swap(a++, b);
                b++;
            }
            while (c >= b && (cmp = q.compare(c, off)) >= 0) {
                if (cmp == 0)
                    q.swap(c, d--);
                c--;
            }
            if (b > c)
                break;
            q.swap(b++, c--);
        }

        // Swap partition elements back to middle
        int s, n = off + len;
        s = Math.min(a - off, b - a);
        vecswap(q, off, b - s, s);
        s = Math.min(d - c, n - d - 1);
        vecswap(q, b, n - s, s);

        // Recursively sort non-partition-elements
        if ((s = b - a) > 1)
            sort1(q, off, k, s);
        if ((s = d - c) > 1)
            sort1(q, n - s, k, s);
    }
416165
private static int[] filterBySetPos(int[] members, int[] bySetPos) {
        members = Util.uniquify(members);
        IntSet iset = new IntSet();
        for (int pos : bySetPos) {
            if (pos == 0) {
                continue;
            }
            if (pos < 0) {
                pos += members.length;
            } else {
                --pos;  // Zero-index.
            }
            if (pos >= 0 && pos < members.length) {
                iset.add(members[pos]);
            }
        }
        return iset.toIntArray();
    }
861461
private static void quickSort1(int off, int len, IntComparator comp, Swapper swapper) {
	// Insertion sort on smallest arrays
	if (len < SMALL) {
		for (int i=off; i<len+off; i++)
		for (int j=i; j>off && (comp.compare(j-1,j)>0); j--) {
		    swapper.swap(j, j-1);
		}
		return;
	}

	// Choose a partition element, v
	int m = off + len/2;       // Small arrays, middle element
	if (len > SMALL) {
		int l = off;
		int n = off + len - 1;
		if (len > MEDIUM) {        // Big arrays, pseudomedian of 9
			int s = len/8;
			l = med3(l,     l+s, l+2*s, comp);
			m = med3(m-s,   m,   m+s, comp);
			n = med3(n-2*s, n-s, n, comp);
		}
		m = med3(l, m, n, comp); // Mid-size, med of 3
	}
	//long v = x[m];
	
	// Establish Invariant: v* (<v)* (>v)* v*
	int a = off, b = a, c = off + len - 1, d = c;
	while(true) {
		int comparison;
		while (b <= c && ((comparison=comp.compare(b,m))<=0)) {
			if (comparison == 0) {
				if (a==m) m = b; // moving target; DELTA to JDK !!!
				else if (b==m) m = a; // moving target; DELTA to JDK !!!
			    swapper.swap(a++, b);
			}
			b++;
		}
		while (c >= b && ((comparison=comp.compare(c,m))>=0)) {
			if (comparison == 0) {
				if (c==m) m = d; // moving target; DELTA to JDK !!!
				else if (d==m) m = c; // moving target; DELTA to JDK !!!
			    swapper.swap(c, d--);
			}
			c--;
		}
		if (b > c) break;
		if (b==m) m = d; // moving target; DELTA to JDK !!!
		else if (c==m) m = c; // moving target; DELTA to JDK !!!
		swapper.swap(b++, c--);
	}

	// Swap partition elements back to middle
	int s, n = off + len;
	s = java.lang.Math.min(a-off, b-a  );  vecswap(swapper, off, b-s, s);
	s = java.lang.Math.min(d-c,   n-d-1);  vecswap(swapper, b,   n-s, s);

	// Recursively sort non-partition-elements
	if ((s = b-a) > 1) 
		quickSort1(off, s, comp, swapper);
	if ((s = d-c) > 1) 
		quickSort1(n-s, s, comp, swapper);
}
1171464
function(array, nodesToMove,
                                                   insertDepth) {
    var firstNode = array.length - 2;
    var nextNode = array.length - 1;
    var currentDepth = (insertDepth == 1) ? 2 : 1;
    var nodesLeftToMove = (insertDepth == 1) ? nodesToMove - 2 : nodesToMove;
    var availableNodes, lastNode, offset, i;

    for (availableNodes = currentDepth << 1;
         availableNodes > 0;
         currentDepth++) {
      lastNode = firstNode;
      firstNode = (firstNode <= nodesToMove) ? firstNode : first (array, lastNode - 1, nodesToMove);

      offset = 0;
      if (currentDepth >= insertDepth) {
        offset = Math.min (nodesLeftToMove, 1 << (currentDepth - insertDepth));
      } else if (currentDepth == (insertDepth - 1)) {
        offset = 1;
        if ((array[firstNode]) == lastNode) {
          firstNode++;
        }
      }

      for (i = availableNodes - (lastNode - firstNode + offset); i > 0; i--) {
        array[nextNode--] = currentDepth;
      }

      nodesLeftToMove -= offset;
      availableNodes = (lastNode - firstNode + offset) << 1;
    }
  }
514697
private static <V> Collection<V> sorted(Iterable<V> source, Comparator<V> comparator, int size)
    {
        V[] vs = (V[]) new Object[size];
        int i = 0;
        for (V v : source)
            vs[i++] = v;
        Arrays.sort(vs, comparator);
        return Arrays.asList(vs);
    }
1053304
public static void quickSort(double[] array, int[] idx, int from, int to) {
		if (from < to) {
			double temp = array[to];
			int tempIdx = idx[to];
			int i = from - 1;
			for (int j = from; j < to; j++) {
				if (array[j] <= temp) {
					i++;
					double tempValue = array[j];
					array[j] = array[i];
					array[i] = tempValue;
					int tempIndex = idx[j];
					idx[j] = idx[i];
					idx[i] = tempIndex;
				}
			}
			array[to] = array[i + 1];
			array[i + 1] = temp;
			idx[to] = idx[i + 1];
			idx[i + 1] = tempIdx;
			quickSort(array, idx, from, i);
			quickSort(array, idx, i + 1, to);
		}
	}
104788
private void select_sort_split(int p, int n) {
        int pa, pb, pi, pn;
        int f, v;

        pa = p; /* pa is start of group being picked out. */
        pn = p + n - 1; /* pn is last position of subarray. */
        while (pa < pn) {
            for (pi = pb = pa + 1, f = KEY(pa); pi <= pn; ++pi)
                if ((v = KEY(pi)) < f) {
                    f = v; /* f is smallest key found. */
                    SWAP(pi, pa); /* place smallest element at beginning. */
                    pb = pa + 1; /* pb is position for elements equal to f. */
                } else if (v == f) { /* if equal to smallest key. */
                    SWAP(pi, pb); /* place next to other smallest elements. */
                    ++pb;
                }
            update_group(pa, pb - 1); /* update group values for new group. */
            pa = pb; /* continue sorting rest of the subarray. */
        }
        if (pa == pn) { /* check if last part is single element. */
            V[start + I[pa]] = pa;
            I[pa] = -1; /* sorted group. */
        }
    }
561010
static void qsort2(int[] keys, int[] values, int lo, int hi) {
            int i = lo;
            int j = hi;
            int pivot = keys[(i+j)/2];
            do {
                while (keys[i] < pivot) i++;
                while (pivot < keys[j]) j--;
                if (i <= j) {
                    int temp1 = keys[i];
                    keys[i] = keys[j];
                    keys[j] = temp1;
                    int temp2 = values[i];
                    values[i] = values[j];
                    values[j] = temp2;
                    i++;
                    j--;
                }
            } while (i <= j);
            if (lo < j) qsort2(keys, values, lo, j);
            if (i < hi) qsort2(keys, values, i, hi);
        }
1296421
public static int binarySearch(Quicksortable qs, int size) {
        int low = 0;
        int high = size-1;

        while (low <= high) {
            int mid = (low + high) >> 1;
            int cmp = qs.compare(mid, -1);

            if (cmp < 0)
            low = mid + 1;
            else if (cmp > 0)
            high = mid - 1;
            else
            return mid; // key found
        }
        return -(low + 1);  // key not found.
    }
104543
private static <T> void insertionSort(List<T> data, Comparator<? super T> comparator, int start, int end) {
    for(int i = start + 1; i < end; i++) {
      for(int j = i; j > start && comparator.compare(data.get(j - 1), data.get(j)) > 0; j--) {
        swap(data, j, j - 1);
      }
    }
  }
76023
public static <T extends Comparable<? super T>> void insertionSort( T[] arr )
    {
        int j;
        for ( int i = 1; i < arr.length; i++ ) {
            T tmp = arr[i];
            for ( j = i; j > 0 && tmp.compareTo(arr[j-1]) < 0; j--) {
                arr[j] = arr[j-1];
            }
            
            if ( j < i ) arr[j] = tmp; 
        }
    }
1301536
public static void heapSort(Quicksortable q, int size) {
        q = reverseQuicksortable(q);
        makeHeap(q, size);
        sortheap(q, size);
    }
1352562
private void ssMintroSort(int PA, int first, int last, int depth) {
        final int STACK_SIZE = SS_MISORT_STACKSIZE;
        StackElement[] stack = new StackElement[STACK_SIZE];
        int Td;// T ptr
        int a, b, c, d, e, f;// SA ptr
        int s, t;
        int ssize;
        int limit;
        int v, x = 0;
        for (ssize = 0, limit = ssIlg(last - first); ; ) {

            if ((last - first) <= SS_INSERTIONSORT_THRESHOLD) {
                if (1 < (last - first)) {
                    ssInsertionSort(PA, first, last, depth);
                }
                if (ssize > 0) {
                    StackElement se = stack[--ssize];
                    first = se.a;
                    last = se.b;
                    depth = se.c;
                    limit = se.d;
                } else {
                    return;
                }

                continue;
            }

            Td = depth;
            if (limit-- == 0) {
                ssHeapSort(Td, PA, first, last - first);

            }
            if (limit < 0) {
                for (a = first + 1, v = T[start + Td + SA[PA + SA[first]]]; a < last; ++a) {
                    if ((x = T[start + Td + SA[PA + SA[a]]]) != v) {
                        if (1 < (a - first)) {
                            break;
                        }
                        v = x;
                        first = a;
                    }
                }

                if (T[start + Td + SA[PA + SA[first]] - 1] < v) {
                    first = ssPartition(PA, first, a, depth);
                }
                if ((a - first) <= (last - a)) {
                    if (1 < (a - first)) {
                        stack[ssize++] = new StackElement(a, last, depth, -1);
                        last = a;
                        depth += 1;
                        limit = ssIlg(a - first);
                    } else {
                        first = a;
                        limit = -1;
                    }
                } else {
                    if (1 < (last - a)) {
                        stack[ssize++] = new StackElement(first, a, depth + 1, ssIlg(a
                            - first));
                        first = a;
                        limit = -1;
                    } else {
                        last = a;
                        depth += 1;
                        limit = ssIlg(a - first);
                    }
                }
                continue;
            }

            // choose pivot
            a = ssPivot(Td, PA, first, last);
            v = T[start + Td + SA[PA + SA[a]]];
            swapInSA(first, a);

            // partition
            for (b = first; (++b < last) && ((x = T[start + Td + SA[PA + SA[b]]]) == v); ) {
            }
            if (((a = b) < last) && (x < v)) {
                for (; (++b < last) && ((x = T[start + Td + SA[PA + SA[b]]]) <= v); ) {
                    if (x == v) {
                        swapInSA(b, a);
                        ++a;
                    }
                }
            }

            for (c = last; (b < --c) && ((x = T[start + Td + SA[PA + SA[c]]]) == v); ) {
            }
            if ((b < (d = c)) && (x > v)) {
                for (; (b < --c) && ((x = T[start + Td + SA[PA + SA[c]]]) >= v); ) {
                    if (x == v) {
                        swapInSA(c, d);
                        --d;
                    }
                }
            }

            for (; b < c; ) {
                swapInSA(b, c);
                for (; (++b < c) && ((x = T[start + Td + SA[PA + SA[b]]]) <= v); ) {
                    if (x == v) {
                        swapInSA(b, a);
                        ++a;
                    }
                }
                for (; (b < --c) && ((x = T[start + Td + SA[PA + SA[c]]]) >= v); ) {
                    if (x == v) {
                        swapInSA(c, d);
                        --d;
                    }
                }
            }

            if (a <= d) {
                c = b - 1;

                if ((s = a - first) > (t = b - a)) {
                    s = t;
                }
                for (e = first, f = b - s; 0 < s; --s, ++e, ++f) {
                    swapInSA(e, f);
                }
                if ((s = d - c) > (t = last - d - 1)) {
                    s = t;
                }
                for (e = b, f = last - s; 0 < s; --s, ++e, ++f) {
                    swapInSA(e, f);
                }

                a = first + (b - a);
                c = last - (d - c);
                b = (v <= T[start + Td + SA[PA + SA[a]] - 1]) ? a : ssPartition(PA, a, c,
                    depth);

                if ((a - first) <= (last - c)) {
                    if ((last - c) <= (c - b)) {
                        stack[ssize++] = new StackElement(b, c, depth + 1, ssIlg(c - b));
                        stack[ssize++] = new StackElement(c, last, depth, limit);
                        last = a;
                    } else if ((a - first) <= (c - b)) {
                        stack[ssize++] = new StackElement(c, last, depth, limit);
                        stack[ssize++] = new StackElement(b, c, depth + 1, ssIlg(c - b));
                        last = a;
                    } else {
                        stack[ssize++] = new StackElement(c, last, depth, limit);
                        stack[ssize++] = new StackElement(first, a, depth, limit);
                        first = b;
                        last = c;
                        depth += 1;
                        limit = ssIlg(c - b);
                    }
                } else {
                    if ((a - first) <= (c - b)) {
                        stack[ssize++] = new StackElement(b, c, depth + 1, ssIlg(c - b));
                        stack[ssize++] = new StackElement(first, a, depth, limit);
                        first = c;
                    } else if ((last - c) <= (c - b)) {
                        stack[ssize++] = new StackElement(first, a, depth, limit);
                        stack[ssize++] = new StackElement(b, c, depth + 1, ssIlg(c - b));
                        first = c;
                    } else {
                        stack[ssize++] = new StackElement(first, a, depth, limit);
                        stack[ssize++] = new StackElement(c, last, depth, limit);
                        first = b;
                        last = c;
                        depth += 1;
                        limit = ssIlg(c - b);
                    }
                }

            } else {
                limit += 1;
                if (T[start + Td + SA[PA + SA[first]] - 1] < v) {
                    first = ssPartition(PA, first, last, depth);
                    limit = ssIlg(last - first);
                }
                depth += 1;
            }

        }

    }
1097700
function wrapPartsIntoGroups(parts, indexes) {
  if (indexes.length === 0) {
    return parts;
  }

  let lastEnd = 0;

  return indexes.reduce((accumulator, index) => {
    const { start, end, alignment, before, after } = index;
    const printedPartsForGrouping = concat([
      before || "",
      concat(parts.slice(start, end)),
      after || ""
    ]);
    const newArray = accumulator.concat(
      parts.slice(lastEnd, start),
      alignment
        ? dedentToRoot(
            group(
              concat([
                align(new Array(alignment).join(" "), printedPartsForGrouping)
              ])
            )
          )
        : group(printedPartsForGrouping),
      end === parts.length - 1 ? parts.slice(end) : ""
    );

    lastEnd = end;

    return newArray;
  }, []);
}
1072788
private static void quickSort(double[] keys, int[] vals, final int start, final int end) {
    final int len = end - start;
    if(len < INSERTION_THRESHOLD) {
      insertionSort(keys, vals, start, end);
      return;
    }
    final int last = end - 1;

    // Choose pivots by looking at five candidates.
    final int seventh = (len >> 3) + (len >> 6) + 1;
    final int m3 = (start + end) >> 1; // middle
    final int m2 = m3 - seventh;
    final int m1 = m2 - seventh;
    final int m4 = m3 + seventh;
    final int m5 = m4 + seventh;

    // Mixture of insertion and merge sort:
    sort5(keys, vals, m1, m2, m3, m4, m5);

    // Move pivot to the front.
    double pivotkey = keys[m3];
    int pivotval = vals[m3];
    keys[m3] = keys[start];
    vals[m3] = vals[start];

    // The interval to pivotize
    int left = start + 1; // Without pivot
    int right = last; // inclusive

    // This is the classic QuickSort loop:
    while(true) {
      // Move duplicates to right partition, i.e. < here, <= below.
      while(left <= right && keys[left] < pivotkey) {
        left++;
      }
      while(left <= right && pivotkey <= keys[right]) {
        right--;
      }
      if(right <= left) {
        break;
      }
      swap(keys, vals, left, right);
      left++;
      right--;
    }
    // right now points to the last element smaller than the pivot.
    // Move pivot back into the appropriate place
    keys[start] = keys[right];
    vals[start] = vals[right];
    keys[right] = pivotkey;
    vals[right] = pivotval;

    // Recursion when more than one element only:
    if(start + 1 < right) {
      quickSort(keys, vals, start, right);
    }
    int rstart = right + 1;
    // Avoid recursing on duplicates of the pivot:
    while(rstart < last && keys[rstart] <= keys[right]) {
      rstart++;
    }
    // Recurse when _more_ than 1 element only
    if(rstart < last) {
      quickSort(keys, vals, rstart, end);
    }
  }