归并排序是通过序列的合并来实现排序的。
对于一个序列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]))