Dual Pivot Quick Sort Java default sorting algorithm
Posted By : Avaneesh Kumar Verma | 23-Sep-2018
What happens when we do Array.sort() in java?. Which Data Structure internally used by Java or say which Data Structure Implemented in Array.sort().Since Java 7 release in 2011, In Array.Sort() default data Structure implemented are Dual PivotQuickSortalgorithm which is an upgrade over the quicksort algorithm.
DualPivotQuickSort is a combination of Insertion Sort and quick sort, Insertion sort faster runtime when a number of elements is small(Array Size). DualPivotQuickSort utilizes this reality hence when a number of elements are <=47 java used Insertion sort algorithm.Dual pivot quickSort Little bit faster than Single pivot quicksort but still worst case complexity is O(n^2) when data already sorted in an increasing or decreasing order.
When Number of elements greater than 47 then Array.sort() used Dual Pivot QuickSort algorithm, In Dual Pivot QuickSort, picks 2 pivots instead of 1. In Quick Sort algorithm we pick 1 pivot elements but in Dual Pivot QuickSort picks 2 pivots elements one is "LP: Left Pivot" and other is "RP: Right Pivot". we partition the array 3 parts around 2 pivots.
1st sub array: items < Left pivot(LP)
2nd sub array : Left pivot(LP) <= items <= Right pivot(RP)
3rd sub array: items >= Right pivot (RP)
Algorithm
LP: Left Pivot
RP: Right Pivot
1.) Left Most elements in an array taken as LP(left pivot) and Rightmost elements are taken as the RP(Right Pivot).
2.) Swap Left pivot (Lp) with Right Pivot if LP greater then RP(if LP> RP).
3.) An array is a partition into 3 sub-array around left and right pivot.
Once a partition is done we perform over 3 stages recursively on three sub-array.
Note:-DualPivotQuickSort class has a threshold of '47' defined for a number of elements in an array. If a number of elements are lesser than a threshold then sorting function uses insertion sort.
Below snippet is from Java docs.
private static final int INSERTION_SORT_THRESHOLD = 47;
Cookies are important to the proper functioning of a site. To improve your experience, we use cookies to remember log-in details and provide secure log-in, collect statistics to optimize site functionality, and deliver content tailored to your interests. Click Agree and Proceed to accept cookies and go directly to the site or click on View Cookie Settings to see detailed descriptions of the types of cookies and choose whether to accept certain cookies while on the site.
About Author
Avaneesh Kumar Verma
Avaneesh is a Software developer Having Knowledge Java , J2EE ,Data Structure and Algorithm ,SQL.