Source code for tryalgo.left_right_inversions

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""\
Left and right inversions in a table
christoph dürr - 2016-2019
"""


# snip{
# pylint: disable=too-many-arguments, missing-docstring
def _merge_sort(tab, tmp, rank, left, right, lo, hi):
    if hi <= lo + 1:             # interval is empty or singleton
        return                   # nothing to do
    mid = lo + (hi - lo) // 2    # divide interval into [lo:mid], [mid:hi]
    _merge_sort(tab, tmp, rank, left, right, lo, mid)
    _merge_sort(tab, tmp, rank, left, right, mid, hi)
    i = lo                       # merge both lists
    j = mid
    k = lo
    while k < hi:
        if i < mid and (j == hi or tab[rank[i]] <= tab[rank[j]]):
            tmp[k] = rank[i]
            right[rank[i]] += j - mid
            i += 1
        else:
            tmp[k] = rank[j]
            left[rank[j]] += mid - i
            j += 1
        k += 1
    for k in range(lo, hi):      # copy sorted segment into original table
        rank[k] = tmp[k]


# pylint: disable=anomalous-backslash-in-string
[docs]def left_right_inversions(tab): """ Compute left and right inversions of each element of a table. :param tab: list with comparable elements :returns: lists left and right. left[j] = the number of i<j such that tab[i] > tab[j]. right[i] = the number of i<j such that tab[i] > tab[j]. :complexity: `O(n log n)` """ n = len(tab) left = [0] * n right = [0] * n tmp = [None] * n # temporary table rank = list(range(n)) _merge_sort(tab, tmp, rank, left, right, 0, n) return left, right
# snip}