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

DualPivot sorting calculates incorrect runs for nearly sorted arrays

    Details

    • Subcomponent:
    • Resolved In Build:
      b119
    • Verification:
      Verified

      Description

      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.

        Attachments

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

          Issue Links

            Activity

              People

              • Assignee:
                psandoz Paul Sandoz
                Reporter:
                amlu Amy Lu
              • Votes:
                0 Vote for this issue
                Watchers:
                8 Start watching this issue

                Dates

                • Created:
                  Updated:
                  Resolved: