[algorithm] 배열에서 반전 계산

이 답변의 주된 목적은 여기에서 찾은 다양한 Python 버전의 속도를 비교하는 것이지만 저도 몇 가지 기여했습니다. (FWIW, 중복 검색을 수행하는 동안이 질문을 발견했습니다).

CPython에서 구현 된 알고리즘의 상대적 실행 속도는 알고리즘의 간단한 분석 및 다른 언어 경험에서 기대하는 것과 다를 수 있습니다. 파이썬은 완전 컴파일 된 언어에서 얻을 수있는 속도에 가까운 속도로 목록 및 기타 컬렉션에서 작동 할 수있는 C로 구현 된 많은 강력한 함수와 메서드를 제공하기 때문에 이러한 작업은 Python으로 “수동으로”구현 된 동일한 알고리즘보다 훨씬 빠르게 실행됩니다. 암호.

이러한 도구를 활용하는 코드는 컬렉션의 개별 항목에 대해 Python 작업으로 모든 작업을 수행하려는 이론적으로 우수한 알고리즘보다 성능이 뛰어난 경우가 많습니다. 물론 처리되는 실제 데이터 양도 이것에 영향을 미칩니다. 그러나 적당한 양의 데이터의 경우 C 속도로 실행되는 O (n²) 알고리즘을 사용하는 코드는 개별 Python 작업으로 대량 작업을 수행하는 O (n log n) 알고리즘을 쉽게 이길 수 있습니다.

이 반전 계산 질문에 대한 많은 게시 된 답변은 mergesort를 기반으로 한 알고리즘을 사용합니다. 이론적으로 이것은 배열 크기가 매우 작지 않는 한 좋은 접근 방식입니다. 그러나 Python의 내장 TimSort (병합 정렬 및 삽입 정렬에서 파생 된 안정적인 하이브리드 정렬 알고리즘)는 C 속도로 실행되며 Python에서 수동으로 코딩 된 병합 정렬은 속도면에서 경쟁 할 수 없습니다.

Niklas B가 게시 한 답변 에서 더 흥미로운 솔루션 중 하나는 내장 정렬을 사용하여 배열 항목의 순위를 결정하고 Binary Indexed Tree (일명 Fenwick 트리)를 사용하여 반전을 계산하는 데 필요한 누적 합계를 저장합니다. 카운트. 이 데이터 구조와 Niklas의 알고리즘을 이해하려는 과정에서 몇 가지 변형을 작성했습니다 (아래 게시 됨). 그러나 나는 또한 적당한 목록 크기의 경우 사랑스러운 Fenwick 트리보다 Python의 내장 함수 를 사용하는 것이 실제로 더 빠르다 는 것을 발견했습니다 sum.

def count_inversions(a):
    total = 0
    counts = [0] * len(a)
    rank = {v: i for i, v in enumerate(sorted(a))}
    for u in reversed(a):
        i = rank[u]
        total += sum(counts[:i])
        counts[i] += 1
    return total

결국 목록 크기가 약 500 개가 sum되면 for루프 내부를 호출하는 O (n²) 측면이 추악한 머리를 뒤로하고 성능이 떨어지기 시작합니다.

Mergesort는 유일한 O (nlogn) 정렬이 아니며, 여러 다른 정렬을 사용하여 반전 계산을 수행 할 수 있습니다. prasadvk의 답변 은 이진 트리 정렬을 사용하지만 그의 코드는 C ++ 또는 그 파생물 중 하나 인 것으로 보입니다. 그래서 파이썬 버전을 추가했습니다. 원래 클래스를 사용하여 트리 노드를 구현했지만 dict가 눈에 띄게 더 빠르다는 것을 발견했습니다. 나는 결국 더 빠른 목록을 사용했지만 코드를 조금 덜 읽기 쉽게 만들었습니다.

treesort의 한 가지 보너스는 mergesort보다 반복적으로 구현하는 것이 훨씬 쉽다는 것입니다. 파이썬은 재귀를 최적화하지 않으며 재귀 깊이 제한이 있습니다 ( 정말 필요한 경우 늘릴 수 있음 ). 물론 Python 함수 호출은 상대적으로 느리기 때문에 속도를 최적화하려는 경우 실용적인 경우 함수 호출을 피하는 것이 좋습니다.

또 다른 O (nlogn) 정렬은 유서 깊은 기수 정렬입니다. 큰 장점은 키를 서로 비교하지 않는다는 것입니다. 그것의 단점은 정수의 연속 시퀀스, 이상적에서 정수의 순열에서 가장 잘 작동한다는 것입니다 range(b**m)어디에 b나는 일종의 읽는 후에 기수에 따라 몇 가지 버전을 추가 일반적으로 2 인 계수의 자리 바꿈, 오프라인 직교 범위 카운팅을하고, 관련 문제 입니다 순열에서 ‘반전’수 를 계산하는 데 연결됩니다 .

기수 정렬을 효과적으로 사용 seq하여 길이 n 의 일반적인 시퀀스에서 반전을 계산하기 range(n)위해와 동일한 수의 반전을 갖는 순열을 만들 수 있습니다 seq. TimSort를 통해 (최악의 경우) O (nlogn) 시간에이를 수행 할 수 있습니다. 트릭은 seq정렬 하여의 인덱스를 순회하는 것 seq입니다. 작은 예를 들어 설명하는 것이 더 쉽습니다.

seq = [15, 14, 11, 12, 10, 13]
b = [t[::-1] for t in enumerate(seq)]
print(b)
b.sort()
print(b)

산출

[(15, 0), (14, 1), (11, 2), (12, 3), (10, 4), (13, 5)]
[(10, 4), (11, 2), (12, 3), (13, 5), (14, 1), (15, 0)]

의 (값, 인덱스) 쌍을 정렬하여 정렬 된 순서에서 원래 순서 로 입력하는 데 필요한 동일한 수의 스왑으로 seq인덱스를 순열했습니다 . 적절한 키 기능 으로 정렬하여 해당 순열을 만들 수 있습니다 .seqseqrange(n)

print(sorted(range(len(seq)), key=lambda k: seq[k]))

산출

[4, 2, 3, 5, 1, 0]

의 메소드 lambda를 사용하여이를 피할 수 있습니다 .seq.__getitem__

sorted(range(len(seq)), key=seq.__getitem__)

이것은 약간 더 빠르지 만 우리가 얻을 수있는 모든 속도 향상을 찾고 있습니다. 😉

아래 코드 timeit는이 페이지의 모든 기존 Python 알고리즘에 대한 테스트와 몇 가지 무차별 대입 O (n²) 버전, Niklas B의 알고리즘에 대한 몇 가지 변형, 물론 mergesort를 기반으로 한 알고리즘에 대한 테스트를 수행합니다 . (기존 답변을 참조하지 않고 썼습니다). 또한 prasadvk의 코드에서 대략적으로 파생 된 목록 기반 트리 정렬 코드와 기수 정렬을 기반으로하는 다양한 기능, 병합 ​​정렬 접근 방식과 유사한 전략을 사용하는 일부, sum또는 Fenwick 트리를 사용 하는 일부 기능이 있습니다.

이 프로그램은 임의의 정수 목록에서 각 함수의 실행 시간을 측정합니다. 또한 각 함수가 다른 함수와 동일한 결과를 제공하고 입력 목록을 수정하지 않는지 확인할 수 있습니다.

각 timeit호출은 3 개의 결과를 포함하는 벡터를 제공합니다. 여기서 살펴볼 주요 값은 최소값이고 다른 값 은 timeit모듈 문서 의 참고에서 논의 된대로 최소값이 얼마나 신뢰할 수 있는지를 나타냅니다 .

불행히도이 프로그램의 출력은이 답변에 포함하기에는 너무 커서 자체 (커뮤니티 위키) 답변에 게시하고 있습니다.

출력은 오래된 Debian 파생 배포판에서 Python 3.6.0을 실행하는 오래된 32 비트 싱글 코어 2GHz 컴퓨터에서 3 번 실행 된 것입니다. YMMV. 테스트 중에 웹 브라우저를 종료하고 다른 작업이 CPU에 미치는 영향을 최소화하기 위해 라우터에서 연결을 끊었습니다.

첫 번째 실행은 목록 크기가 5 ~ 320이고 루프 크기가 ​​4096 ~ 64 인 모든 함수를 테스트합니다 (목록 크기가 두 배가되면 루프 크기가 ​​절반으로 줄어 듭니다). 각 목록을 구성하는 데 사용되는 임의 풀은 목록 자체의 절반 크기이므로 많은 중복 항목 을 얻을 수 있습니다. 반전 계산 알고리즘 중 일부는 다른 것보다 중복에 더 민감합니다.

두 번째 실행에서는 더 큰 목록 (640 ~ 10240)과 고정 루프 크기 8을 사용합니다. 시간을 절약하기 위해 테스트에서 가장 느린 여러 기능을 제거합니다. 내 무차별 O는 (n²) 기능은 있습니다 방법 이 크기에 너무 느리게하고, 이전에 내 코드를 언급 한 바와 같이 사용하는 sum중간 목록에 작은에 잘하지, 단지 큰 목록에 유지할 수 없습니다.

최종 실행은 20480에서 655360까지의 목록 크기와 8 개의 가장 빠른 기능을 포함하는 고정 루프 크기 4를 다룹니다. 40,000 개 이하의 목록 크기의 경우 Tim Babych의 코드가 확실한 승자입니다. 잘 했어요 Tim! Niklas B의 코드는 더 작은 목록에서 패배하지만 좋은 만능 수행자입니다. “파이썬”의 이분법 기반 코드도 꽤 잘 작동하지만, 중복이 많은 거대한 목록에서는 약간 느려 보이지만, 아마도 복제 while를 건너 뛰기 위해 사용 하는 선형 루프 때문일 것입니다 .

그러나 매우 큰 목록 크기의 경우 이분법 기반 알고리즘은 실제 O (nlogn) 알고리즘과 경쟁 할 수 없습니다.

#!/usr/bin/env python3

''' Test speeds of various ways of counting inversions in a list

    The inversion count is a measure of how sorted an array is.
    A pair of items in a are inverted if i < j but a[j] > a[i]

    See /programming/337664/counting-inversions-in-an-array

    This program contains code by the following authors:
    mkso
    Niklas B
    B. M.
    Tim Babych
    python
    Zhe Hu
    prasadvk
    noman pouigt
    PM 2Ring

    Timing and verification code by PM 2Ring
    Collated 2017.12.16
    Updated 2017.12.21
'''

from timeit import Timer
from random import seed, randrange
from bisect import bisect, insort_left

seed('A random seed string')

# Merge sort version by mkso
def count_inversion_mkso(lst):
    return merge_count_inversion(lst)[1]

def merge_count_inversion(lst):
    if len(lst) <= 1:
        return lst, 0
    middle = len(lst) // 2
    left, a = merge_count_inversion(lst[:middle])
    right, b = merge_count_inversion(lst[middle:])
    result, c = merge_count_split_inversion(left, right)
    return result, (a + b + c)

def merge_count_split_inversion(left, right):
    result = []
    count = 0
    i, j = 0, 0
    left_len = len(left)
    while i < left_len and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            count += left_len - i
            j += 1
    result += left[i:]
    result += right[j:]
    return result, count

# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
# Using a Binary Indexed Tree, aka a Fenwick tree, by Niklas B.
def count_inversions_NiklasB(a):
    res = 0
    counts = [0] * (len(a) + 1)
    rank = {v: i for i, v in enumerate(sorted(a), 1)}
    for x in reversed(a):
        i = rank[x] - 1
        while i:
            res += counts[i]
            i -= i & -i
        i = rank[x]
        while i <= len(a):
            counts[i] += 1
            i += i & -i
    return res

# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
# Merge sort version by B.M
# Modified by PM 2Ring to deal with the global counter
bm_count = 0

def merge_count_BM(seq):
    global bm_count
    bm_count = 0
    sort_bm(seq)
    return bm_count

def merge_bm(l1,l2):
    global bm_count
    l = []
    while l1 and l2:
        if l1[-1] <= l2[-1]:
            l.append(l2.pop())
        else:
            l.append(l1.pop())
            bm_count += len(l2)
    l.reverse()
    return l1 + l2 + l

def sort_bm(l):
    t = len(l) // 2
    return merge_bm(sort_bm(l[:t]), sort_bm(l[t:])) if t > 0 else l

# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
# Bisection based method by Tim Babych
def solution_TimBabych(A):
    sorted_left = []
    res = 0
    for i in range(1, len(A)):
        insort_left(sorted_left, A[i-1])
        # i is also the length of sorted_left
        res += (i - bisect(sorted_left, A[i]))
    return res

# Slightly faster, except for very small lists
def solutionE_TimBabych(A):
    res = 0
    sorted_left = []
    for i, u in enumerate(A):
        # i is also the length of sorted_left
        res += (i - bisect(sorted_left, u))
        insort_left(sorted_left, u)
    return res

# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
# Bisection based method by "python"
def solution_python(A):
    B = list(A)
    B.sort()
    inversion_count = 0
    for i in range(len(A)):
        j = binarySearch_python(B, A[i])
        while B[j] == B[j - 1]:
            if j < 1:
                break
            j -= 1
        inversion_count += j
        B.pop(j)
    return inversion_count

def binarySearch_python(alist, item):
    first = 0
    last = len(alist) - 1
    found = False
    while first <= last and not found:
        midpoint = (first + last) // 2
        if alist[midpoint] == item:
            return midpoint
        else:
            if item < alist[midpoint]:
                last = midpoint - 1
            else:
                first = midpoint + 1

# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
# Merge sort version by Zhe Hu
def inv_cnt_ZheHu(a):
    _, count = inv_cnt(a.copy())
    return count

def inv_cnt(a):
    n = len(a)
    if n==1:
        return a, 0
    left = a[0:n//2] # should be smaller
    left, cnt1 = inv_cnt(left)
    right = a[n//2:] # should be larger
    right, cnt2 = inv_cnt(right)

    cnt = 0
    i_left = i_right = i_a = 0
    while i_a < n:
        if (i_right>=len(right)) or (i_left < len(left)
            and left[i_left] <= right[i_right]):
            a[i_a] = left[i_left]
            i_left += 1
        else:
            a[i_a] = right[i_right]
            i_right += 1
            if i_left < len(left):
                cnt += len(left) - i_left
        i_a += 1
    return (a, cnt1 + cnt2 + cnt)

# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
# Merge sort version by noman pouigt
# From https://stackoverflow.com/q/47830098
def reversePairs_nomanpouigt(nums):
    def merge(left, right):
        if not left or not right:
            return (0, left + right)
        #if everything in left is less than right
        if left[len(left)-1] < right[0]:
            return (0, left + right)
        else:
            left_idx, right_idx, count = 0, 0, 0
            merged_output = []

            # check for condition before we merge it
            while left_idx < len(left) and right_idx < len(right):
                #if left[left_idx] > 2 * right[right_idx]:
                if left[left_idx] > right[right_idx]:
                    count += len(left) - left_idx
                    right_idx += 1
                else:
                    left_idx += 1

            #merging the sorted list
            left_idx, right_idx = 0, 0
            while left_idx < len(left) and right_idx < len(right):
                if left[left_idx] > right[right_idx]:
                    merged_output += [right[right_idx]]
                    right_idx += 1
                else:
                    merged_output += [left[left_idx]]
                    left_idx += 1
            if left_idx == len(left):
                merged_output += right[right_idx:]
            else:
                merged_output += left[left_idx:]
        return (count, merged_output)

    def partition(nums):
        count = 0
        if len(nums) == 1 or not nums:
            return (0, nums)
        pivot = len(nums)//2
        left_count, l = partition(nums[:pivot])
        right_count, r = partition(nums[pivot:])
        temp_count, temp_list = merge(l, r)
        return (temp_count + left_count + right_count, temp_list)
    return partition(nums)[0]

# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
# PM 2Ring
def merge_PM2R(seq):
    seq, count = merge_sort_count_PM2R(seq)
    return count

def merge_sort_count_PM2R(seq):
    mid = len(seq) // 2
    if mid == 0:
        return seq, 0
    left, left_total = merge_sort_count_PM2R(seq[:mid])
    right, right_total = merge_sort_count_PM2R(seq[mid:])
    total = left_total + right_total
    result = []
    i = j = 0
    left_len, right_len = len(left), len(right)
    while i < left_len and j < right_len:
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
            total += left_len - i
    result.extend(left[i:])
    result.extend(right[j:])
    return result, total

def rank_sum_PM2R(a):
    total = 0
    counts = [0] * len(a)
    rank = {v: i for i, v in enumerate(sorted(a))}
    for u in reversed(a):
        i = rank[u]
        total += sum(counts[:i])
        counts[i] += 1
    return total

# Fenwick tree functions adapted from C code on Wikipedia
def fen_sum(tree, i):
    ''' Return the sum of the first i elements, 0 through i-1 '''
    total = 0
    while i:
        total += tree[i-1]
        i -= i & -i
    return total

def fen_add(tree, delta, i):
    ''' Add delta to element i and thus
        to fen_sum(tree, j) for all j > i
    '''
    size = len(tree)
    while i < size:
        tree[i] += delta
        i += (i+1) & -(i+1)

def fenwick_PM2R(a):
    total = 0
    counts = [0] * len(a)
    rank = {v: i for i, v in enumerate(sorted(a))}
    for u in reversed(a):
        i = rank[u]
        total += fen_sum(counts, i)
        fen_add(counts, 1, i)
    return total

def fenwick_inline_PM2R(a):
    total = 0
    size = len(a)
    counts = [0] * size
    rank = {v: i for i, v in enumerate(sorted(a))}
    for u in reversed(a):
        i = rank[u]
        j = i + 1
        while i:
            total += counts[i]
            i -= i & -i
        while j < size:
            counts[j] += 1
            j += j & -j
    return total

def bruteforce_loops_PM2R(a):
    total = 0
    for i in range(1, len(a)):
        u = a[i]
        for j in range(i):
            if a[j] > u:
                total += 1
    return total

def bruteforce_sum_PM2R(a):
    return sum(1 for i in range(1, len(a)) for j in range(i) if a[j] > a[i])

# Using binary tree counting, derived from C++ code (?) by prasadvk
# https://stackoverflow.com/a/16056139
def ltree_count_PM2R(a):
    total, root = 0, None
    for u in a:
        # Store data in a list-based tree structure
        # [data, count, left_child, right_child]
        p = [u, 0, None, None]
        if root is None:
            root = p
            continue
        q = root
        while True:
            if p[0] < q[0]:
                total += 1 + q[1]
                child = 2
            else:
                q[1] += 1
                child = 3
            if q[child]:
                q = q[child]
            else:
                q[child] = p
                break
    return total

# Counting based on radix sort, recursive version
def radix_partition_rec(a, L):
    if len(a) < 2:
        return 0
    if len(a) == 2:
        return a[1] < a[0]
    left, right = [], []
    count = 0
    for u in a:
        if u & L:
            right.append(u)
        else:
            count += len(right)
            left.append(u)
    L >>= 1
    if L:
        count += radix_partition_rec(left, L) + radix_partition_rec(right, L)
    return count

# The following functions determine swaps using a permutation of 
# range(len(a)) that has the same inversion count as `a`. We can create
# this permutation with `sorted(range(len(a)), key=lambda k: a[k])`
# but `sorted(range(len(a)), key=a.__getitem__)` is a little faster.

# Counting based on radix sort, iterative version
def radix_partition_iter(seq, L):
    count = 0
    parts = [seq]
    while L and parts:
        newparts = []
        for a in parts:
            if len(a) < 2:
                continue
            if len(a) == 2:
                count += a[1] < a[0]
                continue
            left, right = [], []
            for u in a:
                if u & L:
                    right.append(u)
                else:
                    count += len(right)
                    left.append(u)
            if left:
                newparts.append(left)
            if right:
                newparts.append(right)
        parts = newparts
        L >>= 1
    return count

def perm_radixR_PM2R(a):
    size = len(a)
    b = sorted(range(size), key=a.__getitem__)
    n = size.bit_length() - 1
    return radix_partition_rec(b, 1 << n)

def perm_radixI_PM2R(a):
    size = len(a)
    b = sorted(range(size), key=a.__getitem__)
    n = size.bit_length() - 1
    return radix_partition_iter(b, 1 << n)

# Plain sum of the counts of the permutation
def perm_sum_PM2R(a):
    total = 0
    size = len(a)
    counts = [0] * size
    for i in reversed(sorted(range(size), key=a.__getitem__)):
        total += sum(counts[:i])
        counts[i] = 1
    return total

# Fenwick sum of the counts of the permutation
def perm_fenwick_PM2R(a):
    total = 0
    size = len(a)
    counts = [0] * size
    for i in reversed(sorted(range(size), key=a.__getitem__)):
        j = i + 1
        while i:
            total += counts[i]
            i -= i & -i
        while j < size:
            counts[j] += 1
            j += j & -j
    return total

# - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
# All the inversion-counting functions
funcs = (
    solution_TimBabych,
    solutionE_TimBabych,
    solution_python,
    count_inversion_mkso,
    count_inversions_NiklasB,
    merge_count_BM,
    inv_cnt_ZheHu,
    reversePairs_nomanpouigt,
    fenwick_PM2R,
    fenwick_inline_PM2R,
    merge_PM2R,
    rank_sum_PM2R,
    bruteforce_loops_PM2R,
    bruteforce_sum_PM2R,
    ltree_count_PM2R,
    perm_radixR_PM2R,
    perm_radixI_PM2R,
    perm_sum_PM2R,
    perm_fenwick_PM2R,
)

def time_test(seq, loops, verify=False):
    orig = seq
    timings = []
    for func in funcs:
        seq = orig.copy()
        value = func(seq) if verify else None
        t = Timer(lambda: func(seq))
        result = sorted(t.repeat(3, loops))
        timings.append((result, func.__name__, value))
        assert seq==orig, 'Sequence altered by {}!'.format(func.__name__)
    first = timings[0][-1]
    timings.sort()
    for result, name, value in timings:
        result = ', '.join([format(u, '.5f') for u in result])
        print('{:24} : {}'.format(name, result))

    if verify:
        # Check that all results are identical
        bad = ['%s: %d' % (name, value)
            for _, name, value in timings if value != first]
        if bad:
            print('ERROR. Value: {}, bad: {}'.format(first, ', '.join(bad)))
        else:
            print('Value: {}'.format(first))
    print()

#Run the tests
size, loops = 5, 1 << 12
verify = True
for _ in range(7):
    hi = size // 2
    print('Size = {}, hi = {}, {} loops'.format(size, hi, loops))
    seq = [randrange(hi) for _ in range(size)]
    time_test(seq, loops, verify)
    loops >>= 1
    size <<= 1

#size, loops = 640, 8
#verify = False
#for _ in range(5):
    #hi = size // 2
    #print('Size = {}, hi = {}, {} loops'.format(size, hi, loops))
    #seq = [randrange(hi) for _ in range(size)]
    #time_test(seq, loops, verify)
    #size <<= 1

#size, loops = 163840, 4
#verify = False
#for _ in range(3):
    #hi = size // 2
    #print('Size = {}, hi = {}, {} loops'.format(size, hi, loops))
    #seq = [randrange(hi) for _ in range(size)]
    #time_test(seq, loops, verify)
    #size <<= 1

출력은 여기를 참조하십시오.

답변

def merge(l1,l2):
    l = []
    # global count
    while l1 and l2:
        if l1[-1] <= l2[-1]:
            l.append(l2.pop())
        else:
            l.append(l1.pop())
            # count += len(l2)
    l.reverse()
    return l1 + l2 + l

def sort(l):
    t = len(l) // 2
    return merge(sort(l[:t]), sort(l[t:])) if t > 0 else l

count=0
print(sort([5,1,2,4,9,3]), count)
# [1, 2, 3, 4, 5, 9] 6

def part(l):
    pivot=l[-1]
    small,big = [],[]
    count = big_count = 0
    for x in l:
        if x <= pivot:
            small.append(x)
            count += big_count
        else:
            big.append(x)
            big_count += 1
    return count,small,big

def quick_count(l):
    if len(l)<2 : return 0
    count,small,big = part(l)
    small.pop()
    return count + quick_count(small) + quick_count(big)

def count_inversions(a):
    n = a.size
    counts = np.arange(n) & -np.arange(n)  # The BIT
    ags = a.argsort(kind='mergesort')
    return  BIT(ags,counts,n)

@numba.njit
def BIT(ags,counts,n):
    res = 0
    for x in ags :
        i = x
        while i:
            res += counts[i]
            i -= i & -i
        i = x+1
        while i < n:
            counts[i] -= 1
            i += i & -i
    return  res