docs: static void introspectiveInsertionSort(final int[] a, final int l, final int r) {
      final int length = (r - l) + 1;
      long cost = 0;
      final long costLimit = 8L * length;
      for (int i = l + 1; i <= r; i++) {
        int j = i;
        final long v = a[i] & 0XFFFF_FFFFL; //v must be long
        while ((j >= (l + 1)) && (v < ((a[j - 1]) & 0XFFFF_FFFFL))) {
          a[j] = a[j - 1];
          j -= 1;
        }
        a[j] = (int) v;
        cost += (i - j); // distance moved is a measure of work
  
        if (cost > costLimit) {
          //we need an unsigned sort, but it is linear time and very rarely occurs
          final long[] b = new long[a.length];
          for (int m = 0; m < a.length; m++) { b[m] = a[m] & 0XFFFF_FFFFL; }
          Arrays.sort(b, l, r + 1);
          for (int m = 0; m < a.length; m++) { a[m] = (int) b[m]; }
          // The following sanity check can be used during development
          //int bad = 0;
          //for (int m = l; m < (r - 1); m++) {
          //  final long b1 = a[m] & 0XFFFF_FFFFL;
          //  final long b2 = a[m + 1] & 0XFFFF_FFFFL;
          //  if (b1 > b2) { bad++; }
          //}
          //assert (bad == 0);
          return;
        }
      }
      // The following sanity check can be used during development
      //    int bad = 0;
      //    for (int m = l; m < (r - 1); m++) {
      //      final long b1 = a[m] & 0XFFFF_FFFFL;
      //      final long b2 = a[m + 1] & 0XFFFF_FFFFL;
      //      if (b1 > b2) { bad++; }
      //    }
      //    assert (bad == 0);
    }