-
Enhancement
-
Resolution: Duplicate
-
P4
-
None
-
None
-
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.
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.
- duplicates
-
JDK-8266431 Dual-Pivot Quicksort improvements (Radix sort)
- Open
- relates to
-
JDK-8309130 x86_64 AVX512 intrinsics for Arrays.sort methods (int, long, float and double arrays)
- Resolved