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

Consider using radix sort in DualPivotQuicksort for int[], or even double[]

XMLWordPrintable

    • generic
    • generic

      A DESCRIPTION OF THE PROBLEM :
      Currently DualPivotQuicksort use counting sort for large byte[] or large short[], since couting sort is an O(n) algorithm and dominate QuickSort (which is comparison based sort so can't be better than O(n log n)) when n is large.

      No similar effort is done for int[] although obviously one int can be split into two short's, so int[] can be sorted using counting sort by sort int[] two times -- once for least significant part, once for most significant part, provided the counting sort is implemented in a way that is stable and carries the other half part when sorting. This technique is usually called "radix sort".

      I believe long[] or double[] could also be sorted this way, although the size threshold may be different for them.

      Since int[] or double[] are much common (I believe) than short[] or byte[], I think the benefit is worth the effort.


            psandoz Paul Sandoz
            webbuggrp Webbug Group
            Votes:
            0 Vote for this issue
            Watchers:
            2 Start watching this issue

              Created:
              Updated:
              Resolved: