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

Vladimir Iaroslavski iaroslavski at mail.ru
Tue Nov 10 12:42:55 UTC 2009


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:

Also additional test cases in Sorting class have been added.

Thank you,

More information about the core-libs-dev mailing list