計數逆序對（counting inversions）

兩位朋友各自為同樣的十部電影排名。他們的品味差多少？一個自然的度量是數他們意見相左的配對：A 把電影 X 排在 Y 之上、但 B 把 Y 排在 X 之上的那些配對。把東西重新標號使 A 的順序是 1,2,3,...；那麼在 B 的列表中，逆序對就是任何位置配對 (i, j)，滿足 i < j 但位置 i 的值大於位置 j 的值——一個次序顛倒的配對。數這些就度量了一個列表離排序狀態有多遠。

檢查所有配對是 O(n^2)。巧妙的觀察是，計數逆序對幾乎可以免費地搭上合併排序的便車。跑合併排序；每當合併步驟在左半還有元素剩下時，就從右半取出一個元素，那些仍留在左半的元素每個都比剛取出的大、卻在原順序中排在它前面——所以每一個都是一個逆序對。具體地說，當你複製一個右半元素而左半還剩 k 個元素時，把 k 加到逆序對計數。由於兩半在合併前已各自排序，這一次加法就正確統計了每個跨半逆序對，每次合併 O(n)，而完全在某半內的逆序對由遞迴呼叫計數。總時間 T(n) = 2 T(n/2) + O(n) = O(n log n)。

計數逆序對是「擴增分治演算法、在合併步驟順帶計算額外東西而不增加漸進成本」的模範例子。它量化了排序程度、是排名間 Kendall tau 距離的基礎、為協同過濾相似度評分，也出現在競賽程式設計中。要做對的關鍵微妙處：計數必須在合併的當下進行，並拆成左內、右內、跨界三部分，恰好對應最大子陣列合併的三個分類。