adnils · August 29, 2015 13:58
diff --git a/d3mergesort.html b/d3mergesort.html
 <!DOCTYPE html>
 <meta charset="utf-8">
 <style>

 body {
  margin-top: 225px;
 }

 line {
  stroke: #000;
  stroke-width: 1.5px;
 }

 </style>
 <body>
 <script src="http://d3js.org/d3.v3.min.js"></script>
 <script>

 // Based on http://vis.stanford.edu/protovis/ex/sort.html
 // Based on work by Robert Sedgewick

 var w = 960,
    h = 50;
    
 var 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 = d3.shuffle(d3.range(n)),
    duration = 250;

 var svg = d3.select("body").append("svg")
    .attr("width", w)
    .attr("height", h);

 var line = svg.selectAll("line")
    .data(data)
  .enter().append("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 {
      d3.shuffle(data);
      setTimeout(start, duration + 4000);
    }
  }
 }

 function transform(d, i) {
  return "translate(" + x(i) + "," + h + ")rotate(" + a(d) + ")";
 }

 // 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;
 }

 </script>
	<!DOCTYPE html>
	<meta charset="utf-8">
	<style>

	body {
	margin-top: 225px;
	}

	line {
	stroke: #000;
	stroke-width: 1.5px;
	}

	</style>
	<body>
	<script src="http://d3js.org/d3.v3.min.js"></script>
	<script>

	// Based on http://vis.stanford.edu/protovis/ex/sort.html
	// Based on work by Robert Sedgewick

	var w = 960,
	h = 50;

	var 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 = d3.shuffle(d3.range(n)),
	duration = 250;

	var svg = d3.select("body").append("svg")
	.attr("width", w)
	.attr("height", h);

	var line = svg.selectAll("line")
	.data(data)
	.enter().append("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 {
	d3.shuffle(data);
	setTimeout(start, duration + 4000);
	}
	}
	}

	function transform(d, i) {
	return "translate(" + x(i) + "," + h + ")rotate(" + a(d) + ")";
	}

	// 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;
	}

	</script>