# Optimization of -0.0 and NaN handling in Dual-Pivot Quicksort class for sorting floating-point values

Tue Nov 10 12:42:55 UTC 2009

```Hello,

The optimization of -0.0 and NaN handling in Dual-Pivot Quicksort
was done for sorting float and double values. The sorting of
floating-point values is done in three phases:

1. Move out NaN to the end of array, count -0.0 and convert it to 0.0
2. Sort everything except NaNs
If count of negative zeros is 0, exit.
3. Turn positive zeros back into negative zeros as appropriate

This structure was used also before but in phase 3 standard binary
search (from Arrays) is used. Note that in last phase we know
that at least one zero must be in the array and we consider
part of the array without NaNs. These conditions allows us to
simplify the binary search to:

private static int findAnyZero(float[] a, int low, int high) {
while (true) {
int middle = (low + high) >>> 1;
float middleValue = a[middle];

if (middleValue < 0.0f) {
low = middle + 1;
} else if (middleValue > 0.0f) {
high = middle - 1;
} else { // middleValue == 0.0f
return middle;
}
}
}

Note that there are no checks with converted values to int/long bits
and no check in while loop.

You can find full version of DualPivotQuicksort at the webrev:
http://cr.openjdk.java.net/~alanb/6899694/webrev.00