递归和归并排序

普通的归并(merge)，j将两个有序的数列合并起来，形成一个更大的有序数列。在leetcode有这样

归并排序(merge sort）

      令有序链表A和B，首先比较两个链表里第一个数，如果A中第一个数不大于B中第一个数，那么把A中第一个数放入到C(新链表),并把A中第一个数删除。如果B第一个数更小，则反。

以此类推，直至A和B中的数都被取尽。如果中间，A或者B先被取尽，后面未取的一部分可以直接放入C

图片不宜太长.jpg

假如，A和B不一定是有序的，那又该怎么办呢。如果链表很小，比如说只有一个元素(数字），那么再一个一个排序不就行了。

在归并排序中引入 分治(divide and conquer)。分治，就是将复杂的问题，分解成两个甚至多个规模相同甚至类似的问题，再对子问题细分，直至子问题变得十分简单。

分治算法 更详细的简介

归并排序使用了分治的思想，而其实现的过程却是使用递归来实现的。

        这个只是最经典的2路归并算法，如果将数组分为更多组(假设K组),是k路归并算法。尽管可通过递归树T(n)=kT(n/3)+O(n)来计算其时间复杂度，时间复杂度看起来会少，实际上花费的时间会更多，因为合并功能花费的时间会变得更高。

reference:https://github.com/Jiangjao/python_learn_demo/blob/master/%E9%80%92%E4%                  BB%A3%E4%B8%8E%E5%88%86%E6%B2%BB

                 极客时间 《程序员的数学基础课》