归并排序
归并排序（Merge sort）是创建在合并实际操作上的一种合理的快速排序算法。该优化算法是选用分治法（Divide and Conquer）的一个十分典型性的运用。
做为一种典型性的分而治之观念的优化算法运用，归并排序的完成由二种方式：
由上而下的递归（全部递归的方式都能够用迭代更新重写，因此 就拥有第 2 种方式）；
由上而下的迭代更新；
在《数据结构与算法 JavaScript 描述》中，创作者得出了由上而下的迭代更新方式。可是针对递归法，创作者却觉得：
However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.
殊不知，在 JavaScript 中这类方法不太行得通，由于这一优化算法的递归深层对它而言太深。
说真话，我不会太了解这句话。意思是 JavaScript c语言编译器运行内存很小，递归过深非常容易导致内存溢出吗？敬请有高手可以赐教。
和选择排序一样，归并排序的特性不会受到键入数据信息的危害，但主要表现比选择排序好的多，由于自始至终全是 O(nlogn) 的算法复杂度。成本是必须附加的存储空间。
优化算法流程
- 申请空间，使其尺寸为2个早已排列编码序列之和，该室内空间用于储放合拼后的编码序列；
- 设置2个表针，最开始部位各自为2个早已排列编码序列的起止部位；
- 较为2个表针所偏向的原素，挑选相对性小的原素放进到合拼室内空间，并挪动表针到下一部位；
- 反复流程 3 直至某一表针做到编码序列尾；
- 将另一序列剩余的全部原素立即拷贝到合拼编码序列尾。
Python 编码完成
def mergeSort(arr):
import math
if(len(arr)<2):
return arr
middle = math.floor(len(arr)/2)
left, right = arr[0:middle], arr[middle:]
return merge(mergeSort(left), mergeSort(right))
def merge(left,right):
result = []
while left and right:
if left[0] <= right[0]:
result.append(left.pop(0));
else:
result.append(right.pop(0));
while left:
result.append(left.pop(0));
while right:
result.append(right.pop(0));
return result
