算法技术手册（原书第2 版）

82

｜

第

4

章

4.8.3 解决方案

归并排序

在归并左右两个子数组时，使用了

i

和

j

遍历左侧（和右侧）的元素，并总是

将

A

[

i

]

和

A

[

j

]

中较小的元素复制到正确的位置

result

[

idx

]

。在此过程中，有三类情况需

要考虑：

•

右侧元素遍历结束

(

j

≥

end

)

，在这种情况下，剩余的元素可以从左侧提取。

•

左侧元素遍历结束（

i

≥

mid

），在这种情况下，剩余的元素可以从右侧提取。

•

左侧和右侧均有元素，如果

A

[

i

] <

A

[

j

]

，则插入

A

[

i

]

，否则插入

A

[

j

]

。

一旦循环完成，

result

就有序了，并且其中的元素都来自原始数组

A

[

start

,

end

]

。例

4-10

为

归并排序

的

Python

实现。

例

4-10

：

Python

实现的归并排序

def sort (A):

"""

原地归并排序

A"""

copy = list (A)?

mergesort_array (copy, A, 0, len(A))

def mergesort_array (A, result, start, end):

"""

对于给定范围的数组元素，在内存中进行归并排序

"""

if end-start<2:

return

if end-start == 2:

if result[start] > result[start+1]:

result[start],result[start+1] = result[start+1],result[start] return

mid=(end+start)//2 ...