定義
逆序數為偶數的排列稱為 偶排列；逆序數為奇數的排列稱為 奇排列。 如2431中，21，43，41，31是逆序，逆序數是4，為偶排列。
逆序數的計算
直接計數
計算一個排列的逆序數的直接方法是逐個枚舉逆序，同時統計個數。例如在序列 { 2, 4, 3, 1 } 中，逆序依次為 (2,1)，(4,3)，(4,1)，(3,1)，因此該序列的逆序數為 4。
Visual Basic 6.0 編寫的示例使用的就是直接計數的方法，函式 NiXushu 返回一個字元串的逆序數。
Private Function NiXuShu(ByVal l As String) As Long '逆序數計算
Dim i As Integer, j As Integer, c As Long
Dim n() As Integer
ReDim n(Len(l))
For i = 1 To Len(l)
n(i) = Val(Mid(l, i, 1))
For j = 1 To i - 1
If n(i) < n(j) Then
c = c + 1
End If
Next j
Next i
NiXuShu = c
End Function
歸併排序
直接計數法雖然簡單直觀，但是其時間複雜度是 O(n^2)。一個更快（但稍複雜）的計算方法是在歸併排序的同時計算逆序數。
下面這個 C++ 編寫的例子演示了計算方法。函式 mergeSort() 返回序列的逆序數。
int is1[n],is2[n];// is1為原數組，is2為臨時數組，n為個人定義的長度
long merge(int low,int mid,int high)
{
int i=low,j=mid+1,k=low;
long count=0;
while(i<=mid&&j<=high)
if(is1[i]<=is1[j])// 此處為穩定排序的關鍵，不能用小於
is2[k++]=is1[i++];
else
{
is2[k++]=is1[j++];
count+=j-k;// 每當後段的數組元素提前時，記錄提前的距離
}
while(i<=mid)
is2[k++]=is1[i++];
while(j<=high)
is2[k++]=is1[j++];
for(i=low;i<=high;i++)// 寫回原數組
is1[i]=is2[i];
return count;
}
long mergeSort(int a,int b)// 下標，例如數組int is[5]，全部排序的調用為mergeSort(0,4)
{
if(a<b)
{
int mid=(a+b)/2;
long count=0;
count+=mergeSort(a,mid);
count+=mergeSort(mid+1,b);
count+=merge(a,mid,b);
return count;
}
return 0;
}
