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

produces the output:


(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'];  
    function (a,b) {
      if ( a.toLowerCase() < b.toLowerCase() ) return -1;
      if ( a.toLowerCase() > b.toLowerCase() ) return 1;
      if ( a.toLowerCase()===b.toLowerCase() ) return 0;

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


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
  // Push the remaining item onto tempArr

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!

3 thoughts on “Javascript Array Sort & Random Ordering”

Leave a Reply

Your email address will not be published. Required fields are marked *