JDK-8318005 : Consider using radix sort in DualPivotQuicksort for int[], or even double[]
  • Type: Enhancement
  • Component: core-libs
  • Sub-Component: java.util
  • Priority: P4
  • Status: Closed
  • Resolution: Duplicate
  • OS: generic
  • CPU: generic
  • Submitted: 2023-10-11
  • Updated: 2023-10-12
  • Resolved: 2023-10-12
Related Reports
Duplicate :  
Relates :  
Description
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.



Comments
Moved to JDK for further discussions.
12-10-2023