来自教程：https://time.geekbang.org/column/article/41913

我们对n个元素进行归并排序，需要时间T(n)，

那分解成两个子数组排序的时间都是T(n/2)。

merge()函数合并的时间复杂度是O(n)。

归并排序的时间复杂度计算公式是：

T(1) = C；   n=1 时，只需要常量级的执行时间，所以表示为 C。
T(n) = 2*T(n/2) + n； n>1


如何求T(n)？

我们对T(n/2)一级一级分解：

T(n) = 2*T(n/2) + n
     = 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n
     = 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n
     = 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n
     ......
     = 2^k * T(n/2^k) + k * n
     ......


可以看出：

当时，就是最底层，也就是进行了k次之后达到了最底层。

求出，带入T(n)的公式，求出：，使用大O表示法：T(n) = O(nlogn);

而且归并排序的算法跟有序度无关，所以时间复杂度很稳定都是O(nLogN)；

 

如何计算归并排序算法的时间复杂度？
什么是归并排序？
计算时间复杂度

什么是归并排序？
归并排序的概念十分简单，就是“分而治之”的思想。这里我直接从网上找了一份对归并排序算法的比较好的介绍排序算法

。
计算时间复杂度
关键是怎么计算时间复杂度？

我们在假设数组的长度为n的基础上进行归并排序，假设排序的总共用时为$T[n]$，则：

第一次，将数组对半分，分别对两个子数组进行排序，并合并两个有序数组，所需要的时间为

$T[n]=T[\lceil\frac{n-1}{2}\rceil]+T[\lfloor\frac{n+1}{2}\rfloor]+\Theta[n]$

我们将其简写为

$T[n]=2\cdot{T[\frac{n}{2}]}+\Theta[n]$

同理，第二次，继续将子数组对半分，并分别对两个子子数组进行排序，并合并两个有序数组，所需要的时间为

$T[\frac{n}{2}]=2\cdot{T[\frac{n}{4}]}+\Theta[\frac{n}{2}]$

依照这个规律，我们计算$T[n]、T[\frac{n}{2}]、T[\frac{n}{4}]。。。、T[2]、T[1]$，且最终可得到下面这个式子：

$T[n]=\Theta[n]+2\Theta[\frac{n}{2}]+4\Theta[\frac{n}{4}]+...+n\Theta[1]
T[n]=n+2\cdot\frac{n}{2}+4\cdot\frac{n}{4}+...+n\cdot1$

我们可以把$\Theta[n]$理解为在$n$时间内完成的程序，则

$\begin{aligned}
T[n]&=n+2\cdot\frac{n}{2}+4\cdot\frac{n}{4}+...+n\cdot1 
\\&=n+n+n+...+n
\\&=n\cdot{log_2{n}}
\end{aligned}$

这里，$log_2{n}$是怎么冒出来的？就是因为一共有$log_2{n}$个$n$相乘（不懂的话，自己好好思考一下）。

因此，最终就可得到归并排序算法的时间复杂度为$n\cdot{log_2{n}}$。

归并排序



算法原理

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。



算法分析

排序的思想就是将元素无限拆分，直到无可拆分为止，再将拆分的元素两两按序合并。

归并排序的原理可以通过下面这张图看清楚：





代码实现



/**
 * @Title: mergeSort 
 * @Description: 归并排序 
 * @param: array
 * void @throws
 */
public static void mergeSort(int[] array) {
    int[] temp = new int[array.length];
    sort(array, temp, 0, array.length - 1);
}

/**
 * @Title: sort
 * @Description: 使用归并排序，对array的left~right进行排序
 * @param: array
 * @param: temp
 * @param: left
 * @param: right
 */
private static void sort(int[] array, int[] temp, int left, int right) {
    // 定义待排序中间元素
    int mid = (left + right) / 2;
    if (left < mid) {
        // 递归排序中间元素及左边的元素
        sort(array, temp, left, mid);
    }
    if (mid + 1 < right) {
        // 递归排序中间元素右边的元素
        sort(array, temp, mid + 1, right);
    }
    // 合并左右两边的元素
    merge(array, temp, left, mid, right);
}

/**
 * @Title: merge
 * @Description: 借助temp数组，合并mid元素左右的元素
 * @param: array
 * @param: temp
 * @param: left
 * @param: mid
 * @param: right
 */
private static void merge(int[] array, int[] temp, int left, int mid, int right) {
    // 用于遍历左边元素
    int i = left;
    // 用于遍历右边元素
    int j = mid + 1;
    // 临时变量
    int t = 0;
    while (i <= mid && j <= right) {
        // 将左右两边最小的元素添加到temp数组中
        if (array[i] <= array[j]) {
            temp[t++] = array[i++];
        } else {
            temp[t++] = array[j++];
        }
    }

    while (i <= mid) {
        // 将左边剩余元素添加到temp数组中
        temp[t++] = array[i++];
    }
    while (j <= right) {
        // 将右边剩余元素添加到temp数组中
        temp[t++] = array[j++];
    }
    t = 0;
    // 将temp中的元素全部拷贝到原数组中
    while (left <= right) {
        array[left++] = temp[t++];
    }
}  array[j] = temp;



时间复杂度和算法稳定性

从上面的代码中可以看出每次合并操作的时间复杂度是O(N)，而二叉树的深度是log2N，所以总的时间复杂度是O(N*lgN)。

因为在合并的时候，如果两个数相等，可以将前面的数先放到辅助数组中，所以归并排序是稳定的。

相关代码都在github上:https://github.com/LebronChenX/sort

喜欢这篇文章的朋友，欢迎长按下图关注公众号lebronchen，第一时间收到更新内容。 

算法描述分析：

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

这是官方一点的对于归并排序的定义，简单的来说，我们把要排序的列表或者数组，每一次都给它递归生成n/2有序列表

我们拿例子来看：

有这样一个列表我们按照分治思想，先将它分为俩组



 

 按照这个思路，我们继续将列表分下去



当我们通过递归分到只剩一个元素时，将俩边的元素进行合并成有序的一个列表



接着其他递归出口也将对应的子列表，合并好



一层层向上合并



最后合并成一个列表

复杂度分析：

排序算法时间复杂度的比较图 转载：https://blog.csdn.net/weixin_40596016/article/details/79711682



python 代码：

# -*- coding: utf-8 -*-
"""
Created on 

@author: Administrator
"""
#优化了网上对于合并的函数的复杂，pyhton的宗旨 
#简洁胜过复杂
#Complex is better than complicated.
#利用列表性质
def merge(leftList,rightList): 
    merges = []
    while leftList and rightList: #谁先出完循环结束
        if leftList[-1] >= rightList[-1]:  #将排序好的俩个列表从后放，谁最大谁放在后面
            merges.insert(0,leftList[-1])
            leftList.pop()
        else :
            merges.insert(0,rightList[-1])
            rightList.pop()
    merges=leftList+rightList+merges  #剩余相加即可，切记剩余的是小数要放在前面
    return merges
def mergesort(a):
    if len(a)<=1:
        return a
    mid = len(a)//2
    rightList=mergesort(a[:mid])
    leftList=mergesort(a[mid:])
    return merge(leftList,rightList)

a=[2,15,30,2,5,9,6]
print (mergesort(a))