SortByKey.hs

module SortByKey where

-- Sorts an array by way of a function to extract a limited-range Int
-- key.  This is a stable sort, suitable as a building block for a
-- bottom-up radix sort.
--
-- Runs in O(|bounds| + key function * n) time
sortByKey ::
    (Int, Int) -- minimum and maximum key produced by the key
               -- extraction function
    -> (a -> Int) -- key extraction function
    -> [a] -- values to sort by the key
    -> [a]
sortByKey bounds key xs = foldr (.) id accumulated []
  where
    accumulated = accumArray append id bounds withKeys
    append existing new = existing . (new :)
    withKeys = map (\x -> (key x, x)) xs