1 // Based on http://vis.stanford.edu/protovis/ex/sort.html

     2 // Based on work by Robert Sedgewick

     3 

     4 var w = 960,

     5     h = 50,

     6     n = 240,

     7     x = d3.scale.linear().domain([0, n]).range([h, w - h]),

     8     a = d3.scale.linear().domain([0, n - 1]).range([90 + 60, 270 - 60]),

     9     data = shuffle(d3.range(n)),

    10     duration = 250;

    11 

    12 var vis = d3.select("#chart").append("svg:svg")

    13     .attr("width", w)

    14     .attr("height", h);

    15 

    16 var line = vis.selectAll("line")

    17     .data(data)

    18   .enter().append("svg:line")

    19     .attr("x1", 0)

    20     .attr("y1", 0)

    21     .attr("x2", 0)

    22     .attr("y2", h)

    23     .attr("transform", transform);

    24 

    25 start();

    26 

    27 // Start the animation!

    28 function start() {

    29   var passes = mergesort(data).reverse();

    30 

    31   update();

    32 

    33   function update() {

    34     var pass = passes.pop();

    35 

    36     line.data(pass, Number)

    37       .transition()

    38         .duration(duration)

    39         .attr("transform", transform);

    40 

    41     if (passes.length) {

    42       setTimeout(update, duration);

    43     } else {

    44       shuffle(data);

    45       setTimeout(start, duration + 4000);

    46     }

    47   }

    48 }

    49 

    50 function transform(d, i) {

    51   return "translate(" + x(i) + "," + h + ")rotate(" + a(d) + ")";

    52 }

    53 

    54 // Fisher-Yates shuffle

    55 function shuffle(array) {

    56   var i = array.length, j, t;

    57   while (--i > 0) {

    58     j = ~~(Math.random() * (i + 1));

    59     t = array[j];

    60     array[j] = array[i];

    61     array[i] = t;

    62   }

    63   return array;

    64 }

    65 

    66 //

    67 // Sorts the specified array using bottom-up mergesort, returning an array of

    68 // arrays representing the state of the specified array after each insertion for

    69 // each parallel pass. The first pass is performed at size = 2.

    70 //

    71 function mergesort(array) {

    72   var passes = [],

    73       i,

    74       j,

    75       n = array.length,

    76       m = 1;

    77 

    78   // double the size each pass

    79   while (m < array.length) {

    80     i = j = 0; while (i < array.length) j += merge(i, i += m, i += m);

    81     if (j) passes.push(array.slice());

    82     else m <<= 1;

    83   }

    84 

    85   // Merges two adjacent sorted arrays in-place.

    86   function merge(start, middle, end) {

    87     middle = Math.min(array.length, middle);

    88     end = Math.min(array.length, end);

    89     for (; start < middle; start++) {

    90       if (array[start] > array[middle]) {

    91         var v = array[start];

    92         array[start] = array[middle];

    93         insert(middle, end, v);

    94         return true;

    95       }

    96     }

    97     return false;

    98   }

    99 

   100   // Inserts the value v into the subarray specified by start and end.

   101   function insert(start, end, v) {

   102     while (start + 1 < end && array[start + 1] < v) {

   103       var tmp = array[start];

   104       array[start] = array[start + 1];

   105       array[start + 1] = tmp;

   106       start++;

   107     }

   108     array[start] = v;

   109   }

   110 

   111   return passes;

   112 }