Inversions problem – haskell way

Given an array of numbers A, we need to find the number of distinct pairs such that,
i < j,  A[i] > A[j]
The naive algorithm would be to make ‘n’ choose 2 comparisons and determine the number of inversions in them. This has a worst case complexity of O(n^2).
We can do better than that by modifying merge sort algorithm, which has a worst case complexity of O(nlogn). That takes care of introduction to the problem and the solution.
I learned haskell but never really used it. It was fading away like high school math did. This problem provided the opportunity to dust some manuals and read some bookmarked sites on programming in haskell. The fun I get out of writing small programs in haskell is that, it allows me to think of a problem without knowing how a computer works. All imperative programming languages need you to understand that you manipulate system’s memory to get the desired result.
The following is an implementation of the solution in haskell:
‘imerge’ takes two sorted lists and returns a tuple containing number of inversions present in the merged list and the merged list.

‘imsort’ takes a list and it’s length and returns a tuple containing number of inversions present in the initial list and the sorted list.

imerge :: (Ord a) => [a] -> [a] -> (Int, [a])
imerge [] bs = (0, bs)
imerge as [] = (0, as)
imerge (a:as) (b:bs)
	| a == b = (fst (imerge as bs), a:b:snd (imerge as bs))
	| a < b = (fst (imerge as (b:bs)), a:snd (imerge as (b:bs)))
	| otherwise = (length (a:as) + (fst (imerge (a:as) bs)), b:snd (imerge (a:as) bs))

imsort :: (Ord a) => [a] -> Int -> (Int, [a])
imsort [a] 1 = (0, [a])
imsort a n = ((fst algo) + (fst (imsort (drop r a) (n-r))) + (fst (imsort (take r a) r)), snd algo )
	where r = n `div` 2
              algo = imerge (snd (imsort (take r a) r)) (snd (imsort (drop r a) (n-r)))

sort :: (Ord a) => [a] -> [a]
sort a = snd (imsort a (length a))

inversions :: (Ord a) => [a] -> Int
inversions a = fst (imsort a (length a))

I hope to see some haskell experts come by and comment on the code.

Advertisement