Đếm cặp nghịch đảo bằng đệ quy

Hàm xét phần đầu A[0] tới A[k]. Các cặp trong phần đầu chia thành hai nhóm: cặp đã nằm hoàn toàn trong A[0] tới A[k−1], và cặp mới có chỉ số bên phải là k. ```python def nghich_dao(A, k): if k <= 0: return 0 c = 0 for i in range(k): if A[i] > A[k]: c += 1 return c + nghich_dao(A, k - 1) ``` Gọi `nghich_dao(A,len(A)-1)`. Ở mỗi bước, k là **chỉ số cuối**, không phải số phần tử. Với ví dụ trên, k=3 thêm hai cặp (0,3),(2,3); k=2 không thêm cặp; k=1 thêm (0,1). Tổng là 2+0+1=3. Mỗi cặp được tính đúng một lần ở bước k=j. Khi dãy rỗng, k=−1 nên trả 0; dãy một phần tử cũng chưa có cặp i<j.

Có thể đếm trực tiếp từng cặp i<j: ```python def nghich_dao_lap(A): c = 0 for i in range(len(A) - 1): for j in range(i + 1, len(A)): if A[i] > A[j]: c += 1 return c ``` Hai bản phải cùng cho 3 trên [4,1,4,2]. Cả hai chỉ đọc và không sửa A. Nếu dùng hàm sắp xếp chèn đã học trước khi đếm, A bị đổi thành dãy không giảm và số cặp nghịch đảo trở thành 0; khi cần đếm trên dữ liệu gốc phải giữ đúng dữ liệu ấy.