Quick, reliable pseudo-shuffler

import Data.List
import Data.Function

merge :: [a] -> [a] -> [a]
merge xs [] = xs
merge [] ys = ys
merge (x:xs) (y:ys) = y : x : merge xs ys

main :: IO ()
main = do
  input <- getContents
  mapM_ putStrLn . foldl1 merge $
    sortBy (on compare length) (group . sort $ lines input)