Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-8154049

DualPivot sorting calculates incorrect runs for nearly sorted arrays

XMLWordPrintable

    • b119
    • Verified

      The dual-pivot quicksort used for sorting primitive arrays supports an optimization for arrays over a certain threshold, where before performing the quicksort it determines if the array is nearly sorted and if so performs a merge sort.

      Optimizations to identify nearly sorted arrays were added with JDK-8080945. However, this contains a bug that incorrectly calculates the runs of ascending, transformed descending, and equal elements. Specifically in certain cases the last run was missing, and the array sub-sequence associated with that last run was not included in the merge sort.

        1. javaws.jar
          470 kB
        2. SortTest.java
          5 kB
        3. ta.jar
          28 kB

            psandoz Paul Sandoz
            amlu Amy Lu (Inactive)
            Votes:
            0 Vote for this issue
            Watchers:
            8 Start watching this issue

              Created:
              Updated:
              Resolved: