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


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}