（3） 设{A1，A2，…，An}是集合{1,2，…，n}的置换。如果i＜j且Ai＞Aj，则对（Ai，Aj）被称为置换的“反转”。例如，置换{3，1，4，2}有三个逆：（3,1）、（3,2）和（4,2）。反转表B1、B2、，。。。，置换{A1，A2，…，An}的Bn是通过使Bj是j左边大于j的元素的数量来获得的（换句话说，Bj是第二分量为j的逆的数量）。例如，置换： { 5,9,1,8,2,6,4,7,3 } 有反转表 2 3 6 4 0 2 2 1 0. 因为在1的左边有2个数字，5和9；3个数字，5、9和8，在2的左边；等等。您的任务是将排列转换为其反转表，反之亦然，从反转表转换为相应的排列。（使用分而治之的方法）伪代码实现并给出时间复杂度

以下是将排列转换为反转表的伪代码：

function reverseTable(array A, array B, int n):
    if n = 1:
        return
    m = floor(n/2)
    reverseTable(A[1..m], B[1..m], m)
    reverseTable(A[m+1..n], B[m+1..n], n-m)
    merge(A[1..m], A[m+1..n], B[1..n])
    
function merge(array L, array R, array B):
    i = j = k = 0
    while i < length(L) and j < length(R):
        if L[i] > R[j]:
            B[k] = B[k] + length(L) - i
            j = j + 1
        else:
            i = i + 1
        k = k + 1
    while i < length(L):
        B[k] = B[k] + length(R)
        k = k + 1
        i = i + 1
    while j < length(R):
        k = k + 1
        j = j + 1
        

时间复杂度为O(nlogn)，因为反转表的计算需要merge的过程，而merge的时间复杂度为O(n)。所以，总的时间复杂度为O(nlogn)。