What is the implementation of collections.sort () and arrays.sort () sorting algorithms in Java JDK? Here’s a bit of an explanation of the problem at the source level:

Arrays.sort(

Arrays.sort(), the sort method has a lot of overloads. There are a dozen of them.

public static void sort(int[] a) {
	DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
Copy the code

You can see the DualPivotQuicksort, which translates to biaxial quicksort (we’ll discuss biaxial quicksort later, which is an improvement over the usual quicksort, as well as the three-way quicksort!). Click on it again and you will find this code:

if (right - left < QUICKSORT_THRESHOLD) {
	sort(a, left, right, true);
	return;
}
Copy the code

Found that biaxial quicksort is used if the array length is less than QUICKSORT_THRESHOLD, and the value is 286.

If the value is greater than 286, it will determine whether the sequential ascending or descending order of the array is good or not. If it is good, it will use merge sort, if it is bad, it will use quicksort.

 /*
  * The array is not highly structured,
  * use Quicksort instead of merge sort.
  */   
Copy the code

Now go back to the above decision to use the biaxial quicksort method, click on it again, and find another judgment:

// Use insertion sort on tiny arrays
if(length < INSERTION_SORT_THRESHOLD) {//... }Copy the code

If the size of the array is smaller than INSERTION_SORT_THRESHOLD(47), then insert sort is used, otherwise biaxial quicksort is used!

In summary, if the array length is greater than or equal to 286 and is consistent, merge sort is used, and if the array length is greater than or equal to 286 and is not consistent, biaxial quicksort is used. Biaxial quicksort is used if the length is less than 286 and greater than or equal to 47, and insertion sort is used if the length is less than 47. The schematic diagram is as follows:

Collections.sort(

Collections.sort() will add Arrays:

Java Backend Technology (ID: JavaITWork)1024, you can get it for free! Includes SSM, Spring family bucket, microservices, MySQL, MyCat, cluster, distributed, middleware, Linux, network, multi-threading, Jenkins, Nexus, Docker, ELK and so on free learning video, continue to update!