Problem: Given an array A[1…n], for every i < j, find the number of inversion pairs such that A[i] > A[j]

The most straightforward way would be N^2 traversal (2 lines). Building on top of that naive solution, we can use something that resembles “merge sort”:

1

inversion (l) = inversion (left half of l) + inversion (right half of l) + inversions cross left/right half

import Hedgehog import Hedgehog.Internal.Property (TestLimit(..), ShrinkLimit(..)) importqualified Hedgehog.Gen as Gen importqualified Hedgehog.Range as Range import Control.Monad (liftM2)

-- #elements not following ascending order count_inversion :: [Int] -> Int count_inversion [] = 0 count_inversion (e:es) = length (filter (e>) es) + count_inversion es

count_inversion_merge :: [Int] -> Int count_inversion_merge = fst . count_inversion_merge' where count_inversion_merge' :: [Int] -> (Int, [Int]) count_inversion_merge' [] = (0, []) count_inversion_merge' [x] = (0, [x]) count_inversion_merge' l = let (left, right) = splitAt ((length l) `div` 2) l (left_n, left_sorted) = count_inversion_merge' left (right_n, right_sorted) = count_inversion_merge' right (merge_n, merge_sorted) = merge left_sorted right_sorted (0, []) in (left_n + right_n + merge_n, merge_sorted)