privatestaticfinalint MIN_MERGE =32;static<T>voidsort(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 mergesif(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 =newTimSort<>(a, c, work, workBase, workLen);int minRun =minRunLength(nRemaining);do{// Identify next runint 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 sortassert lo == hi;
ts.mergeForceCollapse();assert ts.stackSize ==1;}
privatestatic<T>intcountRunAndMakeAscending(T[] a,int lo,int hi,
Comparator<?super T> c){assert lo < hi;int runHi = lo +1;if(runHi == hi)return1;// Find end of run, and reverse range if descendingif(c.compare(a[runHi++], a[lo])<0){// Descending// 一开始是递减序列,就找出最长递减序列的最后一个下标while(runHi < hi && c.compare(a[runHi], a[runHi -1])<0)
runHi++;// 逆转前面的递减序列reverseRange(a, lo, runHi);}else{// Ascendingwhile(runHi < hi && c.compare(a[runHi], a[runHi -1])>=0)
runHi++;}return runHi - lo;}
接着进行二分排序:
privatestatic<T>voidbinarySort(T[] a,int lo,int hi,int start,
Comparator<?super T> c){assert lo <= start && start <= hi;if(start == lo)
start++;for(; start < hi; start++){
T pivot = a[start];// Set left (and right) to the index where a[start] (pivot) belongsint left = lo;int right = start;assert left <= right;/*
* Invariants:
* pivot >= all in [lo, left).
* pivot while(left < right){int mid =(left + right)>>>1;if(c.compare(pivot, a[mid])<0)
right = mid;else
left = mid +1;}assert left == right;/*
* The invariants still hold: pivot >= all in [lo, left) and
* pivot int n = start - left;// The number of elements to move// Switch is just an optimization for arraycopy in default caseswitch(n){case2: a[left +2]= a[left +1];case1: a[left +1]= a[left];break;default: System.arraycopy(a, left, a, left +1, n);}
a[left]= pivot;}}