First, I’d like to thanks those who commented on that post, or sent me notes, offering additional analysis. I think we nailed this one. Within a few days of my report Microsoft updated their JavaScript on the browserchoice.eu<\/a> website, fixing the error. But more on that in a minute.<\/p>\n Several commenters mentioned that if you search Google for “javascript random array sort” the first link returned will be a JavaScript tutorial that has the same offending code as Microsoft’s algorithm. This is not surprising. As I said in my original post, this is a well-known mistake. But it is no less a mistake. If you use Google Code Search for the query “0.5 – Math.random()” lang:javascript<\/a> you will find 50 or so other instances of the faulty algorithm. So if anyone else is using this same algorithm, they should evaluate whether it is really sufficiently random for their needs. In some case, such as a children’s game, it might be fine. But know that there are better and faster algorithms available that are not much more complicated to code.<\/p>\n Another thing to note is that the Microsoft Shuffle algorithm is bad enough with 5-elements in the array, but the non-randomness gets more pronounced as you increase the length of the array. Regardless of the size of the array, it appears that on Internet Explorer the 1st element will end up in last place 50% of the time. There are other pronounced patterns as well. You can see this yourself this this test file<\/a>, which allows you to specify the size of the array as well as the number of iterations. Try a 50-element array for 10,000 iterations to get a good sense of how non-random the results can be.<\/p>\n I used that script to run a large test of 1,000,000 iterations of a 1024-element array. The raw results are here<\/a>. I took that table, and using R’s image() function produced a rendering of that matrix. You can see here the clear over-representation at some positions, including (in the lower left) the flip of the first position to last place. (I’m not quite satisfied with this rendering. Maybe someone can get a better-looking visualization of this same data.)<\/p>\n Sometime last week — I don’t know the exact date — Microsoft updated the code for the browser choice website with a new random shuffle algorithm. You see the code, in situ, here<\/a>. The core of it is in this function:<\/p>\n This looks fine to me. I created a new test driver for this routine, which you can try out here<\/a>. Aside from being much faster, it is gives much better results. Here is a run with a million iterations:<\/p>\n <\/p>\nSome random observations<\/h3>\n
![\"\"](\"https:\/\/2d823b65bb.nxcli.io\/blog\/attachments\/shuffle\/heatmap.png\" "\\"Distribution")
<\/p>\nEvaluating Microsoft’s new shuffle<\/h3>\n
\r\nfunction ArrayShuffle(a)\r\n{\r\n var d, c, b=a.length;\r\n while(b)\r\n {\r\n c=Math.floor(Math.random()*b);\r\n d=a[--b];\r\n a[b]=a[c];\r\n a[c]=d\r\n }\r\n}\r\n<\/pre>\nRaw counts<\/h4>\n