Return to Answer

Haskell, 111 94 bytes * 0.8 = 75.2

f%a=fst<$>iterate(\x->(even#x)++(odd#x))(map(\x->(x,f x))a)!!64
f#x=[(i,j`div`2)|(i,j)<-x,f j]

        map(\x->(x,f x))a    -- map each element x of the input list to a pair
                             -- (x,f x), so the given function f is used only once
   iterate (...) (...) !! 64 -- repeatedly apply one step of the radix sort and
                             -- take the 64th iteration
fst<$>                       -- remove the second element of the pair, i.e.
                             -- restore the original element

                             -- one step of the radix sort
\x->(even#x)++(odd#x)        -- partition the list in pairs with even (l) and
                             -- odd (r) second elements and divide the second 
                             -- element of the pairs by 2. Re-concatenate

[(i,j`div`2)|(i,j)<-x,f j]   -- helper function: filter pairs where the second
                             -- element j satisfy predicate f. Adjust j.

Haskell, 111 89 bytes * 0.8 = 71.2

f%a=fst<$>iterate(\x->(even#x)++(odd#x))[(x,f x)|x<-a]!!64
f#x=[(i,j`div`2)|(i,j)<-x,f j]

           [(x,f x)|x<-a]    -- map each element x of the input list to a pair
                             -- (x,f x), so the given function f is used only once
   iterate (...) (...) !! 64 -- repeatedly apply one step of the radix sort and
                             -- take the 64th iteration
fst<$>                       -- remove the second element of the pair, i.e.
                             -- restore the original element

                             -- one step of the radix sort
\x->(even#x)++(odd#x)        -- partition the list in pairs with even and
                             -- odd second elements and divide the second 
                             -- element of the pairs by 2. Re-concatenate

[(i,j`div`2)|(i,j)<-x,f j]   -- helper function: filter pairs where the second
                             -- element j satisfy predicate f. Adjust j.

Haskell, 111 bytes * 0.8 = 88.8

import Data.List
f%a=fst<$>iterate g(map(\x->(x,f x))a)!!64
g x|(l,r)<-partition(even.snd)x=fmap(`div`2)<$>l++r

Usage example: id % [1234,5134,2435,2435,4534,2462,122,45254,4533] -> [122,1234,2435,2435,2462,4533,4534,5134,45254].

        map(\x->(x,f x))a    -- map each element x of the input list to a pair
                             -- (x,f x), so the given function f is used only once
   iterate g (...) !! 64     -- repeatedly apply one step of the radix sort and
                             -- take the 64th iteration
fst<$>                       -- remove the second element of the pair, i.e.
                             -- restore the original element

                             -- one step of the radix sort
(l,r)<-partition(even.snd)x  -- partition the list in pairs with even (l) and
                             -- odd (r) second elements
      fmap(`div`2)<$>l++r    -- divide the second element of the pairs by 2

Haskell, 111 94 bytes * 0.8 = 75.2

f%a=fst<$>iterate(\x->(even#x)++(odd#x))(map(\x->(x,f x))a)!!64
f#x=[(i,j`div`2)|(i,j)<-x,f j]

Usage example (sort on the sum of the lists): sum % [[1,2,3,4], [2,3,4,5], [1], [1,4,8], [9], [0]] -> [[0],[1],[9],[1,2,3,4],[1,4,8],[2,3,4,5]].

        map(\x->(x,f x))a    -- map each element x of the input list to a pair
                             -- (x,f x), so the given function f is used only once
   iterate (...) (...) !! 64 -- repeatedly apply one step of the radix sort and
                             -- take the 64th iteration
fst<$>                       -- remove the second element of the pair, i.e.
                             -- restore the original element

                             -- one step of the radix sort
\x->(even#x)++(odd#x)        -- partition the list in pairs with even (l) and
                             -- odd (r) second elements and divide the second 
                             -- element of the pairs by 2. Re-concatenate

[(i,j`div`2)|(i,j)<-x,f j]   -- helper function: filter pairs where the second
                             -- element j satisfy predicate f. Adjust j.

Haskell, 111 bytes * 0.8 = 88.8

import Data.List
f%a=fst<$>iterate g(map(\x->(x,f x))a)!!64
g x|(l,r)<-partition(even.snd)x=fmap(`div`2)<$>l++r

Usage example: id % [1234,5134,2435,2435,4534,2462,122,45254,4533] -> [122,1234,2435,2435,2462,4533,4534,5134,45254].

Assuming the given functions maps to non-negative 64-bit integers.

This implements binary radix sort.

How it works:

        map(\x->(x,f x))a    -- map each element x of the input list to a pair
                             -- (x,f x), so the given function f is used only once
   iterate g (...) !! 64     -- repeatedly apply one step of the radix sort and
                             -- take the 64th iteration
fst<$>                       -- remove the second element of the pair, i.e.
                             -- restore the original element

                             -- one step of the radix sort
(l,r)<-partition(even.snd)x  -- partition the list in pairs with even (l) and
                             -- odd (r) second elements
      fmap(`div`2)<$>l++r    -- divide the second element of the pairs by 2

Further calling examples:

length % ["Hello","World!","Golf"]
         -> ["Golf","Hello","World!"]

(fromEnum.last) % ["Strings","sorted","on","last","character"]
         -> ["sorted","on","character","Strings","last"]

Haskell, 111 bytes * 0.8 = 88.8

import Data.List
f%a=fst<$>iterate g(map(\x->(x,f x))a)!!64
g x|(l,r)<-partition(even.snd)x=fmap(`div`2)<$>l++r

Usage example: id % [1234,5134,2435,2435,4534,2462,122,45254,4533] -> [122,1234,2435,2435,2462,4533,4534,5134,45254].

Assuming the given functions maps to non-negative 64-bit integers.

This implements binary radix sort.

How it works:

        map(\x->(x,f x))a    -- map each element x of the input list to a pair
                             -- (x,f x), so the given function f is used only once
   iterate g (...) !! 64     -- repeatedly apply one step of the radix sort and
                             -- take the 64th iteration
fst<$>                       -- remove the second element of the pair, i.e.
                             -- restore the original element

                             -- one step of the radix sort
(l,r)<-partition(even.snd)x  -- partition the list in pairs with even (l) and
                             -- odd (r) second elements
      fmap(`div`2)<$>l++r    -- divide the second element of the pairs by 2

Further calling examples:

length % ["Hello","World!","Golf"]
         -> ["Golf","Hello","World!"]

(fromEnum.last) % ["Strings","sorted","on","last","character"]
         -> ["sorted","on","character","Strings","last"] 

maximum % [[1,2,3,4], [2,5,4], [5,5], [4], [6,2], [2,3]]
         -> [[2,3],[1,2,3,4],[4],[2,5,4],[5,5],[6,2]]