private static void stableLimitedQuickSort()

in src/main/java/org/apache/datasketches/tdigest/Sort.java [42:119]

• 48 lines of code
• 12 McCabe index (conditional complexity)

  private static void stableLimitedQuickSort(final double[] keys, final long[] values,
      int start, int end, final int limit) {
    // the while loop implements tail-recursion to avoid excessive stack calls on nasty cases
    while (end - start > limit) {

      final int pivotIndex = start + ThreadLocalRandom.current().nextInt(end - start);
      final double pivotValue = keys[pivotIndex];

      // move pivot to beginning of array
      swap(keys, start, pivotIndex);
      swap(values, start, pivotIndex);

      // use a three way partition because many duplicate values is an important case
      int low = start + 1;   // low points to first value not known to be equal to pivotValue
      int high = end;        // high points to first value > pivotValue
      int i = low;           // i scans the array
      while (i < high) {
        // invariant: values[k] == pivotValue for k in [0..low)
        // invariant: values[k] < pivotValue for k in [low..i)
        // invariant: values[k] > pivotValue for k in [high..end)
        // in-loop:  i < high
        // in-loop:  low < high
        // in-loop:  i >= low
        final double vi = keys[i];
        if (vi == pivotValue && i == pivotIndex) {
          if (low != i) {
            swap(keys, low, i);
            swap(values, low, i);
          } else {
            i++;
          }
          low++;
        } else if (vi > pivotValue || (vi == pivotValue && i > pivotIndex)) {
          high--;
          swap(keys, i, high);
          swap(values, i, high);
        } else {
          i++;
        }
      }
      // assert i == high || low == high therefore, we are done with partition
      // at this point, i == high, [start, low) == pivot,
      // [low, high) < pivot and [high, end) > pivot
      // we have to move the values equal to the pivot into the middle.
      // To do this, we swap pivot values into the top end of the [low, high) range
      // stopping when we run out of destinations or when we run out of values to copy
      int from = start;
      int to = high - 1;
      for (i = 0; from < low && to >= low; i++) {
        swap(keys, from, to);
        swap(values, from++, to--);
      }
      if (from == low) {
        // ran out of things to copy. This means that the last destination is the boundary
        low = to + 1;
      } else {
        // ran out of places to copy to. This means that there are uncopied pivots and the
        // boundary is at the beginning of those
        low = from;
      }

      // now recurse, but arrange it to handle the longer limit by tail recursion
      // we have to sort the pivot values because they may have different weights
      // we can't do that, however until we know how much weight is in the left and right
      if (low - start < end - high) {
        // left side is smaller
        stableLimitedQuickSort(keys, values, start, low, limit);
        // this is really a way to do
        //    quickSort(keys, values, high, end, limit);
        start = high;
      } else {
        stableLimitedQuickSort(keys, values, high, end, limit);
        // this is really a way to do
        //    quickSort(keys, values, start, low, limit);
        end = low;
      }
    }
  }