分治算法求逆序对，写出其伪代码和分析其时间复杂度

分治法是一种将复杂问题分解成小规模相似问题然后递归解决的策略。在求解逆序对这个问题上，经典的分治算法通常是使用归并排序的思想，结合额外的数据结构如哈希表或数组来统计逆序对。

以下是使用Python风格的伪代码：

def mergeSortAndCountInversions(arr):
    if len(arr) <= 1:
        return arr, 0

    mid = len(arr) // 2
    left, inversions_left = mergeSortAndCountInversions(arr[:mid])
    right, inversions_right = mergeSortAndCountInversions(arr[mid:])
    
    merged, new_inversions = merge(left, right)
    return merged, inversions_left + inversions_right + countNewInversions(merged)

def merge(left, right):
    merged = []
    inversion_count = 0
    i, j = 0, 0
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            inversion_count += len(left) - i     # 当右遍历比左遍历元素大，说明有len(left)-i个逆序对
            j += 1
            
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged, inversion_count

# 计算合并后的新逆序对数量
def countNewInversions(merged):
    return sum(merged[i] > merged[j] for i in range(len(merged)) for j in range(i+1, len(merged)))

arr = ...  # 输入数组
sorted_arr, inversion_count = mergeSortAndCountInversions(arr)

时间复杂度分析：
- 归并排序的时间复杂度是O(n log n)，因为每一次分割都会将数组分为两半，并且需要对每个部分进行排序。
- 在merge函数中，合并过程和计算新逆序对的时间复杂度都是线性的，即O(n)，n为剩余未排序部分的长度。

因此，总的时间复杂度是O(n log n)，这是由于归并排序主导了整个过程。不过需要注意的是，实际运行时，计数部分的常数因子相对较小，所以通常可以说整体操作大致是线性对数级别。