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

[Paul Sandoz]

> On 3 May 2016, at 14:50, Aleksey Shipilev <aleksey.shipilev at oracle.com> wrote:
> 
> 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?”
> 

and “real programmers don’t comment code” :-)


> 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;
> }
> 

Yes, that helps a lot, many thanks. I will update accordingly.


> ...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.
> 

Someday i might revisit and rewrite…

Paul.