RFR 8154049: DualPivot sorting calculates incorrect runs for nearly sorted arrays

[Aleksey Shipilev]

On 04/21/2016 04:24 PM, Paul Sandoz wrote:
> Please review:
> 
> http://cr.openjdk.java.net/~psandoz/jdk9/JDK-8154049-dual-pivot-sort-one-off-error/webrev/

Ew. It is a complete brain-twister to understand the original code, the
original improvement, the bug, and the fix -- all four! This is a
manifestation of Kernigan's "Everyone knows that debugging is twice as
hard as writing a program in the first place. So if you're as clever as
you can be when you write it, how will you ever debug it?"

In constructive vein, I think the comment needs to be expanded to:

// These invariants should hold true:
//    run[0] = 0
//    run[<last>] = right + 1; (terminator)

if (count == 0) {
  // A single run of equal elements.
  return;
} else if (count == 1 && run[count] > right) {
  // Either a single ascending or a transformed descending run.
  // Always check that a final run is a proper terminator, otherwise
  // we have an unterminated trailing run, to handle downstream.
  return;
}

right++;
if (run[count] < right) {
  // Corner case: the final run is not a terminator. This may happen
  // if a final run is an equals run, or there is a single-element run
  // at the end. Fix up by adding a proper terminator at the end.
  // Note that we terminate with (right + 1), incremented earlier.
  run[++count] = right;
}

...or somehow rewire the "equals" run logic to add a proper terminator
before breaking from the loop. But this is beyond my capacity this fine
evening.

Thanks,
-Aleksey