归并算法

归并排序（英语：Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法，效率为O(n log n)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。

概述：

采用分治法:

1. 分割：递归地把当前序列平均分割成两半。 

2. 集成：在保持元素顺序的同时将上一步得到的子序列集成到一起（归并）。

图示：

归并排序--图1 归并排序--图2

代码实现：

JAVA递归版：

JAVA-递归版

JAVA迭代版：

JAVA-迭代版

PYTHON：

PYTHON

算法复杂度:

最坏时间复杂度：O(n logn)

最有时间复杂度：O(n logn)

平均时间复杂度：O(n logn)

最坏空间复杂度：O(n)