Write a radix sort

Question

Goal

As the title suggests, write a radix sort function (either MSB or LSB is fine) that accepts two parameters:

• an array of values of any type (you can assume that they are all of the same type / class, etc.)
• a function (or function pointer, depending on your language) that takes a single parameter of the same type as the objects given in the array and returns the coerced integer key of the object.

Implementation may mutate the array or operate out-of-place, but must return the sorted array.

Tips

• If array indexing in your language is affected by the byte-size of each index, you can assume that the objects referenced in the array are pointers rather than values.
• If the size of an array pointed to in a function parameter cannot be determined in your language, then add another parameter to your radix sort signature, passing the size in bytes of your array, or number of elements in your array, whichever you prefer:

void *rsort(void *arr, size_t length, int(*key)(const void *));

Bonus

A bonus reduction of 20% to your score will be given if your implementation memoizes the keys of the objects in the array so that the function provided only needs to be called once for each object in the array.

Example Usage (and test-case)

Assuming an answer was provided in JavaScript, a test-case might look something like this:

/* note that this implementation will not be acceptable as a submission -
 * it is NOT a true radix sort
 */
function myFakeRadixSort(array, key) {
  return array.sort(function(a, b) {
    return key(a) - key(b);
  });
}

/* this will be used as an example key function -
 * you will not need to implement this
 */
function complexity(obj) {
  return JSON.stringify(obj).length;
}

var tree = {
  a: {
    b: {
      c: "a string",
      d: 12
    },
    e: ["an", "array"]
  },
  f: true,
  g: {
    h: null,
    i: {},
    j: {
      k: 500
    }
  }
};

/* another example key function
 */
function index(obj) {
  return JSON.stringify(tree).indexOf(JSON.stringify(obj));
}

var data = [];

/* this is a hack to traverse the object */
JSON.stringify(tree, function(key, value) {
  data.push(value);
  return value;
});

document.write(`<h2>Sorted by "complexity"</h2>`);
document.write(`<pre>${myFakeRadixSort(data, complexity).map(o=>JSON.stringify(o)).join`\n`}</pre>`);
document.write(`<h2>Sorted by "index"</h2>`);
document.write(`<pre>${myFakeRadixSort(data, index).map(o=>JSON.stringify(o)).join`\n`}</pre>`);

tl;dr

Write a radix sort with this signature, or as close as possible to this signature:

void *rsort(void *arr, int(*key)(const void *));

Leaderboards

var QUESTION_ID=71693,OVERRIDE_USER=42091;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+|\d*\.\d+|\d+\.\d*)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;

body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

# Language Name, N bytes

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

# Ruby, <s>104</s> <s>101</s> 96 bytes

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the last number in the header:

# Perl, 43 + 2 (-p flag) = 45 bytes

You can also make the language name a link which will then show up in the leaderboard snippet:

# [><>](http://esolangs.org/wiki/Fish), 121 bytes

Shortest code in bytes wins!

Answer 1

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]

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]].

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

This implements binary radix sort.

How it works:

           [(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.

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]]

Answer 2

ES6, 113 bytes - 20% = 90.4

(a,g)=>(s=(a,i)=>i?s(a.filter(x=>~x[1]&i).concat(a.filter(x=>x[1]&i)),i<<1):a)(a.map(x=>[x,g(x)]),1).map(x=>x[0])

Uses 2 as the radix. Ungolfed:

function rsort(array, key) {
    array = array.map(value => [value, key(value)]);
    // bit becomes zero when the bit falls off the left end
    for (bit = 1; bit; bit <<= 1) {
        zero = array.filter(pair => !(pair[1] & bit));
        one = array.filter(pair => pair[1] & bit);
        array = zero.concat(one);
    }
    return array.map(value => value[0]);
}

Test cases:

f=(a,g)=>(s=(a,i)=>i?s(a.filter(x=>~x[1]&i).concat(a.filter(x=>x[1]&i)),i<<1):a)(a.map(x=>[x,g(x)]),1).map(x=>x[0]);

/* example key function */
function complexity(obj) {
  return JSON.stringify(obj).length;
}

var tree = {
  a: {
    b: {
      c: "a string",
      d: 12
    },
    e: ["an", "array"]
  },
  f: true,
  g: {
    h: null,
    i: {},
    j: {
      k: 500
    }
  }
};

/* another example key function
 */
function index(obj) {
  return JSON.stringify(tree).indexOf(JSON.stringify(obj));
}

var data = [];

/* this is a hack to traverse the object */
JSON.stringify(tree, function(key, value) {
  data.push(value);
  return value;
});

document.write(`<h2>Sorted by "complexity"</h2>`);
document.write(`<pre>${f(data, complexity).map(o=>JSON.stringify(o)).join`\n`}</pre>`);
document.write(`<h2>Sorted by "index"</h2>`);
document.write(`<pre>${f(data, index).map(o=>JSON.stringify(o)).join`\n`}</pre>`);

Answer 3

Pyth, 6 bytes - 20% = 4.8

s.gykQ

This uses radix sort with base 2^64. Since all keys will be non-long positive integers, they are one digit long in base 2^64. We use .g to bucket the numbers, and s to flatten the resulting array. Calls to y are implicitly memoized.

Define the function y with L, which is a lambda b. For example:

Lab5        ## y = lambda b: abs(b-5)
s.gykQ

Less cheaty is this decimal LSB radix sort at 15 bytes - 20% = 12:

us.ge/yk^THGyTQ

Which takes the last twenty decimal digits, plenty for 64-bit numbers.

Try it here.