#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/divide-and-conquer/counting-inversions

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/divide-and-conquer/counting-inversions

Repovive

Counting Inversions - Divide and Conquer | Fundamental Algorithms | Repovive

Repovive.

Fundamental Algorithms8 sections · 294 units2h total

Open in Course

Counting Inversions

A classic D&C application beyond sorting.

Problem: Count pairs $(i, j)$ where $i < j$ but $arr[i] > arr[j]$ .

D&C: Modify merge sort. During merge, when taking from right array, all remaining left elements form inversions.

function countInversions(arr, left, right):
    if left >= right: return 0
    mid = (left + right) / 2
    count = countInversions(arr, left, mid)
    count += countInversions(arr, mid + 1, right)
    count += mergeAndCount(arr, left, mid, right)
    return count

Time: $O(n \log n)$ .