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

// Based on work by Robert Sedgewick

var w = 960,

    h = 50,

    n = 240,

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

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

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

    duration = 250;

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

    .attr("width", w)

    .attr("height", h);

var line = vis.selectAll("line")

    .data(data)

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

    .attr("x1", 0)

    .attr("y1", 0)

    .attr("x2", 0)

    .attr("y2", h)

    .attr("transform", transform);

start();

// Start the animation!

function start() {

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

  update();

  function update() {

    var pass = passes.pop();

    line.data(pass, Number)

      .transition()

        .duration(duration)

        .attr("transform", transform);

    if (passes.length) {

      setTimeout(update, duration);

    } else {

      shuffle(data);

      setTimeout(start, duration + 4000);

    }

  }

}

function transform(d, i) {

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

}

// Fisher-Yates shuffle

function shuffle(array) {

  var i = array.length, j, t;

  while (--i > 0) {

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

    t = array[j];

    array[j] = array[i];

    array[i] = t;

  }

  return array;

}

//

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

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

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

//

function mergesort(array) {

  var passes = [],

      i,

      j,

      n = array.length,

      m = 1;

  // double the size each pass

  while (m < array.length) {

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

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

    else m <<= 1;

  }

  // Merges two adjacent sorted arrays in-place.

  function merge(start, middle, end) {

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

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

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

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

        var v = array[start];

        array[start] = array[middle];

        insert(middle, end, v);

        return true;

      }

    }

    return false;

  }

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

  function insert(start, end, v) {

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

      var tmp = array[start];

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

      array[start + 1] = tmp;

      start++;

    }

    array[start] = v;

  }

  return passes;

}