逆序对
設 A 為一個有 n 個數字的有序集（n>1），其中所有數字各不相同。
如果存在正整數 i, j 使得 1 ≤ i ＜ j ≤ n 而且 A [i] ＞ A [j]，則 <A [i], A [j]> 這一個有序對稱為 A 的一個逆序對，也稱作逆序。逆序對的數量稱作「逆序數」或「反序數」。
例如：數組 <2,3,8,6,1> 的逆序對為：<2,1> <3,1> <8,1> <8,6> <6,1> 共 5 個逆序對。
對於 <2,1>:1 ≤ 1 ＜ 5 ≤ 5 ,A [1] ＞A [5]，所以 <A [1],A [5]> 為一個合法的逆序對。
目前求逆序對數目比較普遍的方法是利用歸併排序做到
  
    
      
        O
        (
        n
        log
        ⁡
        n
        )
      
    
    {\displaystyle O (n\log n)}
  的時間複雜度。
當然，也可以利用樹狀數組、線段樹來實現這種基礎功能。複雜度均為
  
    
      
        O
        (
        n
        log
        ⁡
        n
        )
      
    
    {\displaystyle O (n\log n)}
  。