算法分析：排序算法中key comparisons（关键比较）的判定标准

核心定义 #

关键比较指的是排序过程中直接对两个待排序元素的关键字进行大小判断的操作，这类比较是决定排序流程走向的核心操作，也是排序算法时间复杂度分析的核心统计对象。索引边界判断、变量赋值、索引增减等操作都不属于关键比较。

插入排序计数问题解答 #

你给出的插入排序代码中，while条件里的key < arr[j]确实属于关键比较：这里key是待插入的待排序元素，arr[j]是已排序区间的待比较元素，两者的大小比较直接决定是否要移动元素。
但你当前把comparisons += 1写在循环体内部存在统计误差：
Python的逻辑与and是短路执行的，只有j >= 0判断成立后，才会执行key < arr[j]的比较；如果比较结果为False，不会进入循环体，这次比较就会被漏统计。
修正后的计数写法参考：

def insertionSort(arr):
    comparisons = 0
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0:
            comparisons += 1 # 每次执行key比较前先计数，覆盖所有比较场景
            if key < arr[j]:
                arr[j + 1] = arr[j]
                j -= 1
            else:
                break
        arr[j + 1] = key
    return comparisons

归并排序计数问题解答 #

• 合并阶段第一个while循环里的L[i] < R[j]属于关键比较：是对两个已排序子数组的待排序元素做大小判断，你在这里的计数是正确的，每次进入该循环都完成了一次关键比较，都需要计入。
• 后续两个填充剩余元素的while循环只有索引和数组长度的边界判断，没有待排序元素之间的大小比较，完全不需要计入关键比较，你的理解正确。

混合排序的计数统一规则 #

你研究的快排+插入、归并+插入这类混合排序，只需要遵循同一规则统计即可：所有直接对比两个待排序元素关键字大小的操作都计入，其余操作不计入，不需要因为算法组合改变统计标准。

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