在merge sort（归并排序）实现中应在哪里添加比较计数器？

计数位置说明 #

归并排序过程中所有的元素值比较，仅发生在合并两个有序子数组的阶段，也就是你代码里第一个while循环的left[i] <= right[j]判断逻辑处，每次执行这个判断就对应一次比较，累加计数即可。
后面两个处理剩余元素的while循环不需要做值比较，不需要计入次数。

推荐实现方案（无全局变量，递归返回计数） #

这种方案通过返回值逐层传递各层递归产生的比较次数，逻辑干净无副作用：

def mergesorter(A):
    compare_count = 0
    if len(A) > 1:
        mid = len(A) // 2
        left = A[:mid]
        right = A[mid:]

        # 递归调用累加左右子数组排序的比较次数
        compare_count += mergesorter(left)
        compare_count += mergesorter(right)

        i = j = k = 0
        
        while i < len(left) and j < len(right):
            # 每次进入值判断就计数+1
            compare_count += 1
            if left[i] <= right[j]:
                A[k] = left[i]
                i += 1
            else:
                A[k] = right[j]
                j += 1
            k += 1

        # 剩余元素直接复制，无比较操作
        while i < len(left):
            A[k] = left[i]
            i += 1
            k += 1

        while j < len(right):
            A[k]=right[j]
            j += 1
            k += 1
    # 返回当前层+下层的总比较次数
    return compare_count

调用示例 #

arr = [3,1,4,1,5,9,2,6]
total_compare = mergesorter(arr)
print("排序后数组：", arr)
print("总比较次数：", total_compare)

内容的提问来源于stack exchange，提问作者charles Mahouve