module Main (

    main

) where

    import List hiding (sort)

    main :: IO ()
    main = do
               putStr "Number of items: "
               itemCount <- fmap read getLine
               sorted <- sort (\val1 val2 -> do
                                                 putStr $ "Is "           ++
                                                          show val1       ++
                                                          " better than " ++
                                                          show val2       ++
                                                          "? "
                                                 initAnswer <- getLine
                                                 getDecision initAnswer)
                              [1..itemCount]
               putStr $ unlines [show val ++ " has preference " ++ show rank |
                                 (val,rank) <- sortBy (\(val1,rank1)
                                                        (val2,rank2) -> compare val1 val2) $
                                               zip sorted [1..itemCount]]

    getDecision :: String -> IO Bool
    getDecision "n" = return False
    getDecision "y" = return True
    getDecision _   = do
                          putStr "Illegal answer. Try again. "
                          answer <- getLine
                          getDecision answer

    sort :: (Monad monad) => (val -> val -> monad Bool) -> [val] -> monad [val]
    sort compare []    = return []
    sort compare [val] = return [val]
    sort compare vals  = let

                             (part1,part2) = dissociate vals

                         in do
                                sorted1 <- sort compare part1
                                sorted2 <- sort compare part2
                                merge compare sorted1 sorted2

    dissociate :: [val] -> ([val],[val])
    dissociate []                   = ([],[])
    dissociate [val]                = ([val],[])
    dissociate (val1 : val2 : vals) = let

                                          (subpart1,subpart2) = dissociate vals

                                      in (val1 : subpart1,val2 : subpart2)

    merge :: (Monad monad) => (val -> val -> monad Bool) -> [val] -> [val] -> monad [val]
    merge compare []             []             = return []
    merge compare vals1          []             = return vals1
    merge compare []             vals2          = return vals2
    merge compare (val1 : vals1) (val2 : vals2) = do
                                                      before <- compare val1 val2
                                                      if before
                                                          then do
                                                                   subresult <- merge compare
                                                                                      vals1
                                                                                      (val2 : vals2)
                                                                   return (val1 : subresult)
                                                          else do
                                                                   subresult <- merge compare
                                                                                      (val1 : vals1)
                                                                                      vals2
                                                                   return (val2 : subresult)