Haskell merge sort inversions
General review tips:


It'd be better to document your code. In particular functions like

union :: ([Int], Int) -&gt; ([Int], Int) -&gt; ([Int], Int)


need documentation - it's not clear which Int has what purpose at all without examining the source.
Some of your functions are polymorphic (sndhalf), others not. Why? I'd suggest to have all types consistent. Either just sort Ints, or make the types as generic as possible, for example

union :: (Ord a) =&gt; ([a], Int) -&gt; ([a], Int) -&gt; ([a], Int)


Notice how this generality also makes the types easier to understand.
I'd suggest to wrap list + its inversion count into a newtype such as:

newtype List a = List [a] Int


This makes the code better structured, and also allows you to use smart
constructors, if you decide
so.
Investigate Haskell's
sort
for inspiration.


Now specific to performance:
- For each pass you traverse the list several times,
which can impact the performance considerably. In particular: take and
length in fsthalf, the same in sndhalf. Also length in mergeSort. This
makes it 5 traversals before the merging pass. I'd try to reduce this number.


Matching on length is wasteful, if you need just to distinguish if it's 0 or 1, you traverse the whole list needlessly:

mergeSort (s, c) | length s `elem` [0, 1]  = (s, c)


Instead:

mergeSort ([], _) = ([], 0)
mergeSort (xs@[_], _) = (xs, 1)
...

Make sure you're compiling with -O.


I hope this helps!