Solution
= Solution
Use <merge sort>, then project the second component of each <pair>. Under the ordinary <Haskell Ord class> instance for pairs, “ascending” means <lexicographic order>, requiring both component types to be ordered:
``
sort :: (Ord a, Ord b) => [(a,b)] -> [b]
sort = map snd . mergeSort
mergeSort :: Ord a => [a] -> [a]
mergeSort [] = []
mergeSort [x] = [x]
mergeSort xs = merge (mergeSort left) (mergeSort right)
where (left,right) = splitAt (length xs `div` 2) xs
merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys)
| x <= y = x : merge xs (y:ys)
| otherwise = y : merge (x:xs) ys
``
If the intended convention is to sort only by the first component as a <sort key>, replace `x <= y` by `fst x <= fst y` and specialize the merge routines to pairs. The weaker signature is then `sort :: Ord a => [(a,b)] -> [b]`, and equal keys keep their original order. These conventions differ when first components tie; the question does not explicitly specify that tie rule.