Liệt kê cặp nghịch đảo và chỉ số gốc

Để liệt kê cặp chỉ số của dữ liệu ban đầu, mỗi phần tử đi cùng bản ghi (giá trị,chỉ số gốc). So sánh và trộn theo giá trị nhưng giữ chỉ số đi theo phần tử. Khi giá trị phải nhỏ hơn, mỗi bản ghi trái còn lại sinh một cặp chỉ số gốc. Vì các phần tử trái ban đầu đứng trước phần tử phải, các cặp này thỏa i<j. Từ cặp chỉ số (i,j), đọc A gốc để có cặp giá trị (A[i],A[j]). Không dùng vị trí đã đổi sau sắp xếp như chỉ số của dãy gốc.

```python def pair_merge(B, C): # Mỗi bản ghi là (giá trị, chỉ số gốc), hai dãy đã sắp theo giá trị. result, pairs = [], [] i = j = 0 while i < len(B) and j < len(C): if B[i][0] <= C[j][0]: result.append(B[i]) i += 1 else: result.append(C[j]) pairs.extend((B[t][1], C[j][1]) for t in range(i, len(B))) j += 1 result.extend(B[i:]) result.extend(C[j:]) return result, pairs ``` B[t][0] là giá trị và B[t][1] là chỉ số gốc. Khi B[i][0]>C[j][0], dòng pairs.extend thêm từng cặp (B[t][1],C[j][1]) với t chạy từ i tới cuối B. Mỗi cặp đều phải được ghi, thay vì chỉ cộng một số lượng.

```python def pair_sort(records): if len(records) <= 1: return records, [] mid = len(records) // 2 B, pairsL = pair_sort(records[:mid]) C, pairsR = pair_sort(records[mid:]) merged, pairsM = pair_merge(B, C) return merged, pairsL + pairsM + pairsR ``` ```python def inversion_indices(A): records = [(value, i) for i, value in enumerate(A)] _, pairs = pair_sort(records) return pairs ``` pair_sort trả cả bản ghi đã sắp xếp và danh sách cặp. inversion_indices tạo nhãn gốc trước khi gọi; A gốc không bị sửa. Thứ tự các cặp trong kết quả có thể khác cách duyệt i,j, nhưng cần đủ và không trùng cặp chỉ số.