Javascript Array Sort & Random Ordering

Recently a colleague and I were looking at some Javascript code that randomizes a list of elements. The code did this by creating an array of list-item elements, and then passing a comparison function that returns a random result to the array.sort() method. Unfortunately, the random order was anything but random: after reloading the page 50 times, the distribution was skewed heavily towards the original array ordering.

In case you don’t feel like reading my entire exploration of this topic, I’ll give you the short version:
Don’t use array.sort() to randomize arrays! There are methods of randomizing arrays that produce better (i.e. more random) results, and that are (probably) faster.

I was completely unaware that an array.sort() method existed in Javascript. By default it sorts in lexicographical order. For example:

<script type="text/javascript">
  var arr = ['apple','Zorro','petunia','cat','Adam','123'];
  document.write(arr.sort());
</script>

produces the output:

123,Adam,Zorro,apple,cat,petunia

(Zorro preceding apple because the ASCII value for Z is 90 and the ASCII value for a is 97.)

Simple! Useful! But there is more that can be done. You can pass a function to the array.sort() method that will determine the sort order:

<script type="text/javascript">
  var arr = ['apple','cat','Adam','123','Zorro','petunia'];  
  document.write(arr.sort(
    function (a,b) {
      if ( a.toLowerCase() < b.toLowerCase() ) return -1;
      if ( a.toLowerCase() > b.toLowerCase() ) return 1;
      if ( a.toLowerCase()===b.toLowerCase() ) return 0;
    }
  ));
</script>

Now the sort is case-insensitive and produces the output:

123,Adam,apple,cat,petunia,Zorro

A not-so-random sort
The sort that did not produce random results observed that the comparison function passed to array.sort() is expected to return one of three values:

• -1 (a is less than b)
• 0 (a is equal to b)
• 1 (a is greater than b)

The function passed to array.sort() was something like this:

function () { return Math.floor(Math.random()*3)-1; }

That meant that, approximately two-thirds of the time, the 2 items being compared were determined to be in the proper order (or equal), and therefore did not change places in the list. This is the new order of our original list, sorted 100 times using this method:

Order:	1st	2nd	3rd	4th	5th	6th
apple	52	27	14	2	4	1
Zorro	29	39	25	3	2	2
petunia	8	26	48	8	8	2
cat	7	4	4	43	28	14
Adam	3	2	7	28	34	26
123	1	2	2	16	24	55

Items at the beginning of the list tend to stay at the beginning, and those at the end tend to stay at the end. Not very random.

A random sort
The following function always returns either a -1 or a 1, which I assumed at first would always rearrange the items in the array:

function () { if (Math.random()<.5) return -1; else return 1; }

This is the new order of our original list, sorted 100 times using this method:

Order:	1st	2nd	3rd	4th	5th	6th
apple	27	31	14	12	10	6
Zorro	20	19	30	9	11	11
petunia	26	17	18	13	9	17
cat	12	17	10	23	19	19
Adam	7	7	18	26	25	17
123	8	9	10	17	26	30

That’s less predictable, but still not random! Half the time, the two items being compared seen as being in the correct order (when the comparison function returns -1). What can we do to get a truly random sort?

Answer: don’t use array.sort()
My method, which I borrowed from a card-shuffling script I created, is to create an empty array, and add random elements to it from the existing array (removing each one as it is selected):

<script type="text/javascript">
  var arr = ['apple','cat','Adam','123','Zorro','petunia']; 
  var n = arr.length;
  var tempArr = [];
  for ( var i = 0; i < n-1; i++ ) {
    // The following line removes one random element from arr
    // and pushes it onto tempArr
    tempArr.push(arr.splice(Math.floor(Math.random()*arr.length),1)[0]);
  }
  // Push the remaining item onto tempArr
  tempArr.push(arr[0]);
  arr=tempArr;
</script>

The I ran this 100 times and compiled the new frequency distribution:

Order:	1st	2nd	3rd	4th	5th	6th
apple	14	18	17	18	16	17
Zorro	16	19	11	19	16	19
petunia	17	19	19	22	15	8
cat	18	16	22	11	22	11
Adam	24	11	16	16	12	21
123	11	17	15	14	19	24

Finally–that looks random!

But there’s more: the Javascript (ECMAScript) specifications leave the sort method up to the implementation (i.e. the web browser).

Someone asked on Stack Overflow which algorithms the various browsers use (see Javascript Array.sort implementation?), where it was reported that Firefox uses merge sort. [A good choice, in my opinion, as it produces a stable sort–although the specifications do not require a stable sort, developers and users might expect it.]

My tests, iterating 1000 times over the second array.sort() randomization method listed above, confirmed that Firefox is using an O(n log n) algorithm:

Array Size	Average # of calls to the comparison function
10	16.956
100	316.665
1000	4635.883
10000	63295.287

The randomization method that avoids array.sort(), inserting random items into a new array, loops just n-1 times. I will not go so far as to say that one method is faster than the other for smaller arrays, as I have not timed any of the above tests. I suspect that it is.

In short: don’t hack array.sort() to randomize an array. There are better ways to do it!