由图可知，排序有序数组为线性的
package Cap2_2;import edu.princeton.cs.introcs.StdDraw;
import edu.princeton.cs.introcs.StdOut;
import edu.princeton.cs.introcs.StdRandom;
import Cap1.Stopwatch;
import Cap2_1.Selection;
import Cap2_1.sortTemplate;public class Merge extends sortTemplate{private static int cnt=0; // 访问数组的次数private static Comparable[] aux;public static void sort(Comparable[] a){aux = new Comparable[a.length];sort(a, 0, a.length-1);}private static void sort(Comparable[] a, int lo, int hi){ //自顶向下if(hi<=lo) return;int mid = lo + (hi-lo)/2;sort(a, lo, mid);sort(a, mid+1, hi);if(less(a[mid], a[mid+1])) return; //优化2merge(a, lo, mid, hi);}public static void sort2(Comparable[] a){ //自下向上int N = a.length;aux = new Comparable[N];for(int sz=1; sz<N; sz+=sz)for(int lo=0; lo+sz<N; lo+=sz+sz)merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));}public static void merge(Comparable[] a, int lo, int mid, int hi){int i=lo, j=mid+1;for(int k=lo;k<=hi;k++) {aux[k]=a[k];cnt++;}for(int k=lo;k<=hi;k++){if (i>mid) a[k]=aux[j++];else if (j>hi) a[k]=aux[i++];else if (less(aux[i], aux[j])) a[k]=aux[i++];else a[k]=aux[j++];cnt++;}}public static void main(String[] args) {// TODO Auto-generated method stubStdDraw.setXscale(0, 512);StdDraw.setYscale(-5, 50000);double lastC1=0, lastC2=0;for(int i=1;i<=512;i++){int N=i;Integer[] a = new Integer[N];for(int j=0;j<N;j++)a[j]=j;
// StdRandom.shuffle(a);Merge m = new Merge();m.sort(a);assert m.isSorted(a);int c1 = m.cnt;StdDraw.setPenColor(StdDraw.RED);StdDraw.line((i-1), lastC1, i, c1);}}}