surpassing.hs

-- shiny and exciting O(n log n) algorithm

-- the n parameter and the idea to use something like merge sort is from Bird
-- both of those things are really clever
join    :: Ord a => Int -> [(a, Int)] -> [(a, Int)] -> [(a, Int)]
join 0 ax [] = ax               -- n corresponds to length b, so if b is empty n = 0
join n [] bx = bx
-- something like merge sort but slightly different
join n ax@((a, ac):as) bx@((b, bc):bs)
	| a <  b = (a, ac + n) : join n as bx
	-- n corresponds to the length of b, so when moving on with b, decrement n
	| a >= b = (b, bc) : join (n - 1) ax bs

-- dividing happens here
table' [x] = [(x, 0)]
table' xs  = join b_len (table' a) (table' b) where
	len    = length xs
	a_len  = len `div` 2
	(a, b) = splitAt a_len xs
	b_len  = len - a_len        -- a_len and b_len differ when len is odd

msc'        :: Ord a => [a] -> Int
msc' xs      = maximum $ map snd (table' xs)



main = do
	putStrLn $ show $ msc' [82, 74, 17, 93, 96, 20, 25, 55, 15, 24, 25, 56]