Underlying the collections. sort method is the arrays.sort method called.
Write an example to look at the source:
public static void main(String[] args) {
List<String> strings = Arrays.asList("6"."1"."3"."1"."2"); Collections.sort(strings); //sort is herefor(String string : strings) { System.out.println(string); }}Copy the codeTracing the code, we find that collections.sort calls the list.sort method:
@SuppressWarnings("unchecked")
public static <T extends Comparable<? super T>> void sort(List<T> list) {
list.sort(null);
}
Copy the codeArrays.sort(a,c) :
public static <T> void sort(T[] a, Comparator<? super T> c) {
if(c == null) { sort(a); // My breakpoint is this method}else {
if (LegacyMergeSort.userRequested)
legacyMergeSort(a, c);
elseTimSort.sort(a, 0, a.length, c, null, 0, 0); }}Copy the code— — — — — — — — — — — — — — — — — — — — — — — — — I actually go breakpoints in the show — — — — — — — — — — — — start — — — — — — — — — — — — –
Sort (a);
public static void sort(Object[] a) {
if (LegacyMergeSort.userRequested)
legacyMergeSort(a);
elseComparableTimSort.sort(a, 0, a.length, null, 0, 0); // Then the breakpoint is this step}Copy the codeSort (a, 0, a.length, null, 0, 0);
static void sort(Object[] a, int lo, int hi, Object[] work, int workBase, int workLen) { assert a ! = null && lo >= 0 && lo <= hi && hi <= a.length; int nRemaining = hi - lo;if (nRemaining < 2)
return; // Arrays of size 0 and 1 are always sorted
// If array is small, do a "mini-TimSort" with no merges
if(nRemaining < MIN_MERGE) { int initRunLen = countRunAndMakeAscending(a, lo, hi); binarySort(a, lo, hi, lo + initRunLen); // The breakpoint takes this stepreturn;
}
Copy the codeGo in, binarySort(a, lo, hi, lo + initRunLen); And then we end up here, finishing sorting
@SuppressWarnings({"fallthrough"."rawtypes"."unchecked"})
private static void binarySort(Object[] a, int lo, int hi, int start) {
assert lo <= start && start <= hi;
if (start == lo)
start++;
for(; start < hi; start++) { Comparable pivot = (Comparable) a[start]; // Set left (and right) to the indexwhere a[start] (pivot) belongs
int left = lo;
int right = start;
assert left <= right;
/*
* Invariants:
* pivot >= all in [lo, left).
* pivot < all in [right, start).
*/
while (left < right) {
int mid = (left + right) >>> 1;
if (pivot.compareTo(a[mid]) < 0)
right = mid;
else
left = mid + 1;
}
assert left == right;
/**
* The invariants still hold: pivot >= all in [lo, left) and
* pivot < all in [left, start), so pivot belongs at left. Note
* that if there are elements equal to pivot, left points to the
* first slot after them -- that's why this sort is stable. * Slide elements over to make room for pivot. */ int n = start - left; // The number of elements to move // Switch is just an optimization for arraycopy in default case switch (n) { case 2: a[left + 2] = a[left + 1]; case 1: a[left + 1] = a[left]; break; default: System.arraycopy(a, left, a, left + 1, n); } a[left] = pivot; }}Copy the codeMy breakpoint ends with binarySort in the ComparableTimSort class.
— — — — — — — — — — — — — — — — — — — — — — — — — I actually go breakpoints on the surface show — — — — — — — — — — — — end — — — — — — — — — — — — –
— — — — — — — — — — — — — — — — — — — — — — — — — the following is a description of the other posts — — — — — — — — — — — — start — — — — — — — — — — — — —
Arrays.sort(a,c) :
public static <T> void sort(T[] a, Comparator<? super T> c) { if (c == null) { sort(a); } else { if (LegacyMergeSort.userRequested) legacyMergeSort(a, c); else TimSort.sort(a, 0, a.length, c, null, 0, 0); }}Copy the codeNo write comparator c, trace LegacyMergeSort as follows:
/**
* Old merge sort implementation can be selected (for
* compatibility with broken comparators) using a system property.
* Cannot be a static boolean in the enclosing class due to
* circular dependencies. To be removed in a future release.
*/
static final class LegacyMergeSort {
private static final boolean userRequested =
java.security.AccessController.doPrivileged(
new sun.security.action.GetBooleanAction(
"java.util.Arrays.useLegacyMergeSort")).booleanValue();
}
Copy the codeIs an old merge sort, we use the following method timsor.sort () :
static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c, T[] work, int workBase, int workLen) { assert c ! = null && a ! = null && lo >= 0 && lo <= hi && hi <= a.length; int nRemaining = hi - lo; if (nRemaining < 2) return; // Arrays of size 0 and 1 are always sorted // If array is small, do a "mini-TimSort" with no merges if (nRemaining < MIN_MERGE) { int initRunLen = countRunAndMakeAscending(a, lo, hi, c); binarySort(a, lo, hi, lo + initRunLen, c); return; } /** * March over the array once, left to right, finding natural runs, * extending short natural runs to minRun elements, and merging runs * to maintain stack invariant. */ TimSort<T> ts = new TimSort<>(a, c, work, workBase, workLen); int minRun = minRunLength(nRemaining); do { // Identify next run int runLen = countRunAndMakeAscending(a, lo, hi, c); // If run is short, extend to min(minRun, nRemaining) if (runLen < minRun) { int force = nRemaining <= minRun ? nRemaining : minRun; binarySort(a, lo, lo + force, lo + runLen, c); runLen = force; } // Push run onto pending-run stack, and maybe merge ts.pushRun(lo, runLen); ts.mergeCollapse(); // Advance to find next run lo += runLen; nRemaining -= runLen; } while (nRemaining ! = 0); // Merge all remaining runs to complete sort assert lo == hi; ts.mergeForceCollapse(); assert ts.stackSize == 1; }Copy the code— — — — — — — — — — — — — — — — — — — — — — — — — it is a description of the other posts — — — — — — — — — — — — end — — — — — — — — — — — — –
The underlying implementation of both collections.sort and arrays.sort is TimSort, which is new in jdk1.7 and used to be merge sort. The TimSort algorithm finds subsequences of sorted data, sorts the rest, and merges them.
Colletions. The sort (list) and Arrays. Sort (T [])
Colletions.sort() actually turns the list into an array, and then calls arrays.sort () to return to the list. In ps.jdk8, lists now have their own sort() method, like ArrayList, which uses its own array, while LinkedList, CopyOnWriteArrayList, still copies a List.
Array.sort () : quicksort for primitive types (int[],double[],char[],byte[]) and merge sort for Object types (Object[]). Why use a different algorithm?
The progress of the JDK7
In JDK7, quicksort is upgraded to double-benchmark quicksort (double-benchmark quicksort vs three-way quicksort); Merge sort is upgraded to TimSort, an improved version of merge sort, a JDK self-evolution.
The progress of JDK8
ParallelSort () function is added for large sets. Fork-join framework is used to make full use of multi-cores to split and merge large sets. TimSort and DualPivotQuickSort are still used for small contiguous fragments.
TimSort:
Timsort is a hybrid algorithm that incorporates merge sort and insertion sort. It was introduced by Tim Peters in 2002 and has been built into Python since version 2.3, as well as Java SE 7, Android, and GNU Octave. In simple terms, this algorithm can be summarized as two steps: 1) The first step is to divide the array to be sorted into runs. Of course, run cannot be too short. If the length is less than the minrun threshold, insert sort is used for expansion. 2) The second step is to push run onto the stack, when the length of run at the top of the stack meets: RunLen [n-2] <= runLen[n-1] + runLen[n] or runLen[n-1] <= runLen[n] merges the two short runs into a new run, and the sorting is complete when only the top element is left.
PS: Record it for the time being, and then analyze the sorting algorithm carefullyCopy the code