归并排序是通过序列的合并来实现排序的。

       对于一个序列a1 a2 a2 … an，我们可以首先把它们看成一系列的只有一个元素的有序子序列a1;a2;a3;…;an，我们让a1和a2合并，a3和a4合并，依次类推，最后得到一个有序子序列的序列a1 a2;a3 a4;a5 a6;…;an-1 an，接下来让a1 a2和a3 a4合并，a5 a6和a7 a8合并，以此类推，得到一个更大有序子序列的序列a1 a2 a3 a4;a5 a6 a7 a8;…;an-3 an-2 an-1 an，按照同样的逻辑继续合并，直至最后得到唯一一个序列，它就是排好序的结果序列。   

       算法实现的难点和需要注意的地方在于边界情形，子序列两两配对的时候，可能最后有一个子序列落单了，找不到另一个子序列了，还有两个子序列进行合并时，我们交替得把两个序列的切片首尾接在一起，要注意对最后一个切片的处理。    

       下面是代码：

python">def mergesort(source):dest = [0] * len(source)endpos = len(source)rsize = 1while rsize < len(source):lpos, rpos, pos = 0, rsize, 0lendpos, rendpos = rsize, min(rpos + rsize, endpos)while lpos < endpos and rpos < endpos:while lpos < lendpos and rpos < rendpos:if source[lpos] <= source[rpos]:dest[pos] = source[lpos]lpos += 1else:dest[pos] = source[rpos]rpos += 1pos += 1if lpos < lendpos:dest[pos:pos + (lendpos - lpos)] = source[lpos:lendpos]pos += lendpos - lposlpos = lendposif rpos < rendpos:dest[pos:pos + (rendpos - rpos)] = source[rpos:rendpos]pos += rendpos - rposrpos = rendposlpos, rpos = rendpos, min(rendpos + rsize, endpos)lendpos, rendpos = min(lpos + rsize, endpos), min(rpos + rsize, endpos)if lpos < endpos:dest[pos:] = source[lpos:]rsize *= 2source, dest = dest, sourcereturn sourceprint(mergesort([2, 1, 4, 3, 5, 6, 3, 1,0]))