python-3.x - python（就地）合并排序实现

Question

我正在尝试实现合并排序，以便对列表进行就地排序：

from typing import List, Tuple

def merge_sort(tab: List[int], low:int, end:int) -> None:
    if end > low + 1:
        mid = (low + end) // 2
        merge_sort(tab, low, mid)
        merge_sort(tab, mid, end)
        
        # merging the two sorted halves
        i, j, k = low, mid, low
        while (i < mid) and (j < end):
            if tab[i] < tab[j]:
                tab[k] = tab[i]
                i = i + 1
            else:
                tab[k] = tab[j]
                j = j + 1
            k = k + 1
        
        while (i < mid):
            tab[k] = tab[i]
            i = i + 1
            k = k + 1

        while (j < end):
            tab[k] = tab[j]
            j = j + 1
            k = k + 1

很遗憾：

tab = [54, 26, 93, 17, 77, 31, 44, 55, 20]
merge_sort(tab, 0, len(tab))

将选项卡转换为：

[17, 17, 17, 17, 20, 20, 20, 20, 20]

谁能帮我理解我做错了什么？

标签： python-3.xalgorithm