将分为三步来进行分析

• 找出归并排序方法
• 分析源码
• 附上网上找的时序图

一、找出Collections.sort()实际排序的方法

// 1.这里是入口，还有一个重载方法传入一个比较器，用作比较，可以暂时忽略
public static <T extends Comparable<? super T>> void sort(List<T> list) {
        // 进入第二步
        list.sort(null);
}

// 2.list.sort() 可以看到底层用的其实是Arrays.sort()
// 这里需要注意的是，Arrays.sort()是个重载方法，当参数是基本数据类型和Object时，所用到的排序是不一样的，可以分开看一下
@SuppressWarnings({"unchecked", "rawtypes"})
    default void sort(Comparator<? super E> c) {
        Object[] a = this.toArray();
        // 进入第三步
        Arrays.sort(a, (Comparator) c);
        ListIterator<E> i = this.listIterator();
        for (Object e : a) {
            i.next();
            i.set((E) e);
        }
    }

// 3.没什么好说的，咱们研究的是Comparator为null的情况
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);
        }
}

// 4.第四步
public static void sort(Object[] a) {
        // 这个是一个环境变量，在jvm参数中配置的，jdk1.7之后默认是false
        // 但是我们这次研究的就是归并排序，所以直接点进去看就行了
        if (LegacyMergeSort.userRequested)
            // 归并排序
            legacyMergeSort(a);
        else
            ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
}

二、分析归并排序源码，看注释！！

// 请注意，这是一个递归方法，请按照递归方法的思路去理解
// src 是一个从dest  clone出来的数组，用来在递归中做排序的载体
private static void mergeSort(Object[] src,
                                  Object[] dest,
                                  int low,
                                  int high,
                                  int off) {
        int length = high - low;

        // 1.当长度小于7，直接插入排序比较快，所以直接使用插入排序即可
        if (length < INSERTIONSORT_THRESHOLD) {
            for (int i=low; i<high; i++)
                for (int j=i; j>low &&
                         ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
                    swap(dest, j, j-1);
            return;
        }

        int destLow  = low;
        int destHigh = high;
        low  += off;
        high += off;
        int mid = (low + high) >>> 1;
        // 2.递归中到达这一步肯定是因为长度比较大
        // 所以归并排序在这里进行了二分，分别将前一半排序，后一半也排序
        // 如果前一半长度还是比7大，那就递归的时候继续分，直到比7小，递归才算结束
        mergeSort(dest, src, low, mid, -off);
        mergeSort(dest, src, mid, high, -off);

        // 3.这也是递归中的一步，因为经过上两行的递归，现在前半部分和后半部分都已经是有序的了，那么只要前半部分的最后一位，比后半部分的第一位还小，不就说明前后现在有序么，直接将src数组拷贝到dest即可（当然这里讨论的是默认升序的情况）
        if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
            System.arraycopy(src, low, dest, destLow, length);
            return;
        }

        // 4.在递归中，如果第三步不满足，那就要对前后两部分进行归并排序了
        // 怎么归并呢？以升序为例子
        // 归并排序其实就是对两个有序的数组，每次只比较两个的头部，哪个比较小，就把哪个取出来，然后再次比较两个数组的头部，知道两个数组的值都被取完，整个大数组就排好序了，下边几行代码就是做这个的
        for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
            if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
                dest[i] = src[p++];
            else
                dest[i] = src[q++];
        }
}

时序图

时序图

排序示例

四、既然说到了sort，下一章分析下TimeSort源码

链接