Implement 'MergeSort + Count Inversions' algorithm on a 1-D array

count_array_inversions.py

#!/usr/bin/env python3


def merge_count_split_inversions(left_sorted: list, right_sorted: list, lst_len: int) -> tuple:
    """
    Perform merge of two sorted lists and count inversions while merging

    >>> merge_count_split_inversions([2], [1], 2)
    ([1, 2], 1)
    >>> merge_count_split_inversions([1, 3, 5], [2, 4, 6], 6)
    ([1, 2, 3, 4, 5, 6], 3)
    >>> merge_count_split_inversions([1, 2], [3, 4, 5], 5)
    ([1, 2, 3, 4, 5], 0)
    """
    sorted_lst, split_inversions, i, j = [], 0, 0, 0
    for _ in range(lst_len):
        next_left = left_sorted[i] if i < (lst_len // 2) else None
        next_right = right_sorted[j] if j < lst_len - (lst_len // 2) else None
        if (next_left is not None and next_right is not None and next_left <= next_right) or next_right is None:
            sorted_lst.append(next_left)
            i += 1
        else:
            sorted_lst.append(next_right)
            j += 1
            split_inversions += (lst_len // 2) - i if next_left is not None else 0
    return sorted_lst, split_inversions


def sort_count_array_inversions(lst: list) -> tuple:
    """
    Counts the number of inversions in `lst`

    >>> sort_count_array_inversions([2, 1])
    ([1, 2], 1)
    >>> sort_count_array_inversions([1, 3, 5, 2, 4, 6])
    ([1, 2, 3, 4, 5, 6], 3)
    """
    if (lst_len := len(lst)) == 1:
        return lst, 0
    else:
        left_sorted, left_inversions = sort_count_array_inversions(
            lst[: (lst_len // 2)]
        )
        right_sorted, right_inversions = sort_count_array_inversions(
            lst[(lst_len // 2) :]
        )
        sorted_lst, split_inversions = merge_count_split_inversions(left_sorted, right_sorted, lst_len)
    return sorted_lst, left_inversions + right_inversions + split_inversions

The merge_count_split_inversions subroutine is $O(n)$ time complexity, so just like Merge Sort, counting inversions on a 1-D array is $O(n \log n)$!