algorithm - 如何计算大型数据集中的倒置？

Question

以下内容适用于最多 1000 个元素的所有列表。然而，它的真正目的是处理非常大的列表，100'000 或更有效。当这样的列表传递给函数时，一切都卡住了!任何线索为什么会这样？

这也与:Merge sort to count split inversions in Python有关

这是我的代码...

import operator

def merge_and_count_split_inv(left, right, compare):
    result = []
    split_inversions = []
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if compare(left[i], right[j]):
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            k = i
            while k < len(left):
                split_inversions.append((left[k], right[j]))
                k += 1
            j += 1
    while i < len(left):
        result.append(left[i])
        i += 1
    while j < len(right):
        result.append(right[j])
        j += 1
    return result, split_inversions

def sort_and_count_inversions(L, compare=operator.lt):
    if len(L) < 2:
        return L[:], []
    else:
        middle_index = len(L)/ 2
        a, left = sort_and_count_inversions(L[:middle_index], compare)
        b, right = sort_and_count_inversions(L[middle_index:], compare)
        c, merged = merge_and_count_split_inv(a, b, compare)
    return c, left+right+merged

Answer 1

有一次我想计算一个数组的倒置数只要10^6。这是我在 C++ 中完成这项工作的代码片段。 cnt 保存反转计数的总数。

int ary[1000006];
long cnt;

void merge(int p, int q, int r) {  
    int i, ll, rr, n1, n2;

    n1 = q - p + 1;
    n2 = r - q;

    vector < int > left, right;

    for (i = 0; i < n1; i++) left.push_back(ary[p + i]);
    left.push_back(2147483647);     //ends with largest possible value

    for (i = 0; i < n2; i++) right.push_back(ary[q + i + 1]);
    right.push_back(2147483647);    //ends with largest possible value

    for (i = p, ll = 0, rr = 0; i <= r; i++) {
        if (left[ll] <= right[rr]) ary[i] = left[ll++];
        else {
            ary[i] = right[rr++];
            cnt += n1 - ll;     // number of items remaining in left
        }
    }

    left.clear();
    right.clear();
}

void merge_sort(int p, int r) {
    if (p < r) {
        int q = (p + r) / 2;
        merge_sort(p, q);
        merge_sort(q + 1, r);
        merge(p, q, r);
    }
}