Migration to java 11 continued

 The following section now discusses a few APIs from the JDK 11, their benefits and the preparatory work.

The Arrays api includes a faster and more powerful data structure. All the methods for manipulating arrays including sorting and searching are available as earlier. The sorting algorithm used is Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley and Joshua Bloch. This algorithm has the same O(nlogn) as in the family of quicksort algorithms but is faster than traditional ones for a broader workload.

The traditional algorithm consisted of a single pivot where all elements less than the pivot come before the element and all elements after the pivot come after it and the sub-arrays are recursively sorted.

With the dual pivot variation, there are two pivots which are chosen as say the first and the last element. The pivots have to be sorted otherwise they are swapped.  The range between the pivots is broken down into non-overlapping sub-ranges denoted by sentinels at index L, K and G progressively between the far left and the far right.

The subrange between left+1 to L –1 have elements less than P1

The subrange between L to K-1 have elements >= P1 and <= P2

The subrange between K to G can have any arbitrary remaining elements

The subrange between G+1 to right-1 have elements > P2

This way the arbitrary elements in the third sub-range above is shrunk by placing the element in one of the other three sub-ranges after comparing it with the two pivots. The L, K and G are advanced as the third sub-range is shrunk.

The first pivot element is then swapped with the last element of the first sub-range above.

The second pivot element is then swapped with the first element of the last sub-range above.

The steps are repeated recursively for each sub-range.

The key thing to note here is that for relatively large arrays the complexity remains somewhat similar but everyday programmers generally use this algorithm for small array sizes. The authors took the approach that with a threshold for array length as 27, insertion sort is preferable over all other sorting methods. In JDK 8, this threshold was set to 47.