private static void quickSort0()

in core/src/main/java/org/apache/mahout/math/Sorting.java [297:409]

• 85 lines of code
• 22 McCabe index (conditional complexity)

  private static void quickSort0(int start, int end, IntComparator comp, Swapper swap) {
    int length = end - start;
    if (length < 7) {
      insertionSort(start, end, comp, swap);
      return;
    }
    int middle = (start + end) / 2;
    if (length > 7) {
      int bottom = start;
      int top = end - 1;
      if (length > 40) {
        // for lots of data, bottom, middle and top are medians near the beginning, middle or end of the data
        int skosh = length / 8;
        bottom = med3(bottom, bottom + skosh, bottom + (2 * skosh), comp);
        middle = med3(middle - skosh, middle, middle + skosh, comp);
        top = med3(top - (2 * skosh), top - skosh, top, comp);
      }
      middle = med3(bottom, middle, top, comp);
    }

    int partitionIndex = middle; // an index, not a value.
    
    // regions from a to b and from c to d are what we will recursively sort
    int a = start;
    int b = a;
    int c = end - 1;
    int d = c;
    while (b <= c) {
      // copy all values equal to the partition value to before a..b.  In the process, advance b
      // as long as values less than the partition or equal are found, also stop when a..b collides with c..d
      int comparison;
      while (b <= c && (comparison = comp.compare(b, partitionIndex)) <= 0) {
        if (comparison == 0) {
          if (a == partitionIndex) {
            partitionIndex = b;
          } else if (b == partitionIndex) {
            partitionIndex = a;
          }
          swap.swap(a, b);
          a++;
        }
        b++;
      }
      // at this point [start..a) has partition values, [a..b) has values < partition
      // also, either b>c or v[b] > partition value

      while (c >= b && (comparison = comp.compare(c, partitionIndex)) >= 0) {
        if (comparison == 0) {
          if (c == partitionIndex) {
            partitionIndex = d;
          } else if (d == partitionIndex) {
            partitionIndex = c;
          }
          swap.swap(c, d);

          d--;
        }
        c--;
      }
      // now we also know that [d..end] contains partition values,
      // [c..d) contains values > partition value
      // also, either b>c or (v[b] > partition OR v[c] < partition)

      if (b <= c) {
        // v[b] > partition OR v[c] < partition
        // swapping will let us continue to grow the two regions
        if (c == partitionIndex) {
          partitionIndex = b;
        } else if (b == partitionIndex) {
          partitionIndex = d;
        }
        swap.swap(b, c);
        b++;
        c--;
      }
    }
    // now we know
    // b = c+1
    // [start..a) and [d..end) contain partition value
    // all of [a..b) are less than partition
    // all of [c..d) are greater than partition

    // shift [a..b) to beginning
    length = Math.min(a - start, b - a);
    int l = start;
    int h = b - length;
    while (length-- > 0) {
      swap.swap(l, h);
      l++;
      h++;
    }

    // shift [c..d) to end
    length = Math.min(d - c, end - 1 - d);
    l = b;
    h = end - length;
    while (length-- > 0) {
      swap.swap(l, h);
      l++;
      h++;
    }

    // recurse left and right
    length = b - a;
    if (length > 0) {
      quickSort0(start, start + length, comp, swap);
    }

    length = d - c;
    if (length > 0) {
      quickSort0(end - length, end, comp, swap);
    }
  }