Skip to content

Instantly share code, notes, and snippets.

@AlexMost
Last active August 29, 2015 14:01
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save AlexMost/d0cf75d312808c778576 to your computer and use it in GitHub Desktop.
Save AlexMost/d0cf75d312808c778576 to your computer and use it in GitHub Desktop.
-- split inversions
invSplit':: (Ord a) => Int -> [a] -> [a] -> ([a], Int)
invSplit' i xs [] = (xs, i)
invSplit' i [] ys = (ys, i)
invSplit' i f@(x:xs) s@(y:ys)
| x > y =
let (sorted, ni) = invSplit' (i + (length f)) f ys in (y: sorted, ni)
| x <= y =
let (sorted, ni) = invSplit' i xs s in (x: sorted, ni)
inv:: (Ord a) => [a] -> ([a], Int)
inv [x] = ([x], 0)
inv lst = (splitLst, splitCount + firstCount + lastCount)
where
(sortedFirst, firstCount) = inv first
(sortedLast, lastCount) = inv last
(splitLst, splitCount) = invSplit' 0 sortedFirst sortedLast
(first, last) = splitAt (quot (length lst) 2) lst
-- | The main entry point.
main :: IO ()
main = putStrLn $ show $ inv [1, 3, 5, 2, 4, 6]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment