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

Complete code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import           Hedgehog
import           Hedgehog.Internal.Property (TestLimit(..), ShrinkLimit(..))
import qualified Hedgehog.Gen as Gen
import qualified 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)

    merge :: [Int] -> [Int] -> (Int, [Int]) -> (Int, [Int])
    merge (x:xs) (y:ys) (acc, sorted)
      | x > y     = merge (x:xs) ys (acc + length (x:xs), sorted ++ [y])
      | otherwise = merge xs (y:ys) (acc                , sorted ++ [x])
    merge xs ys (acc, sorted) = (acc, sorted ++ xs ++ ys)

prop_check :: Property
prop_check = withTests (TestLimit 1000) . property $
  forAll gen_list >>= liftM2 (===) count_inversion count_inversion_merge
  where
    gen_list = Gen.list (Range.linear 0 100) $ Gen.element [1..500]

main = do
  check prop_check
-- output
-- ✓ <interactive> passed 1000 tests.