mbostock/.block

## .block
license: gpl-3.0

## README.md

      
    Raw
  

              README.md
            
          
    An improved animation of mergesort. As the name suggests, the algorithm merges sorted arrays, starting with arrays of length 1 and doubling at each step. The two subarrays currently being merged are shown in black.

  
## index.html
<!DOCTYPE html>
<meta charset="utf-8">
<style>

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

.line--inactive {
  stroke: #ddd;
  stroke-width: 1px;
}

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

var n = 200,
    array = d3.shuffle(d3.range(n)),
    actions = mergesort(array.slice()).reverse();

var margin = {top: 180, right: 40, bottom: 180, left: 40},
    width = 960 - margin.left - margin.right,
    height = 500 - margin.top - margin.bottom;

var y = d3.scale.ordinal()
    .domain([1, 0])
    .rangeRoundBands([height, 0], .3);

var x = d3.scale.ordinal()
    .domain(d3.range(n))
    .rangePoints([0, width]);

var a = d3.scale.linear()
    .domain([0, n - 1])
    .range([-45, 45]);

var svg = d3.select("body").append("svg")
    .attr("width", width + margin.left + margin.right)
    .attr("height", height + margin.top + margin.bottom)
  .append("g")
    .attr("transform", "translate(" + margin.left + "," + margin.top + ")");

var line = svg.append("g")
    .attr("class", "line")
  .selectAll("line")
    .data(array.map(function(v, i) {
      return {
        value: v,
        index: i,
        array: 0
      };
    }))
  .enter().append("line")
    .attr("transform", transform)
    .attr("y2", -y.rangeBand());

var line0 = line[0],
    line1 = new Array(n);

var transition = d3.transition()
    .duration(75)
    .each("start", function start() {
      var action = actions.pop();
      switch (action.type) {
        case "merge": {
          d3.selectAll(line0).attr("class", function(d, i) { return action.left <= i && i < action.end ? null : "line--inactive"; });
          break;
        }
        case "copy": {
          var i = action[0],
              j = action[1],
              e = line1[j] = line0[i],
              d = e.__data__;
          d.index = j;
          d.array = (d.array + 1) & 1;
          transition.each(function() { d3.select(e).transition().attr("transform", transform); });
          break;
        }
        case "swap": {
          var t = line0;
          line0 = line1;
          line1 = t;
          break;
        }
      }
      if (actions.length) transition = transition.transition().each("start", start);
    });

function transform(d) {
  return "translate(" + x(d.index) + "," + y(d.array) + ")rotate(" + a(d.value) + ")";
}

function mergesort(array) {
  var actions = [],
      n = array.length,
      array0 = array,
      array1 = new Array(n);

  for (var m = 1; m < n; m <<= 1) {
    for (var i = 0; i < n; i += (m << 1)) {
      merge(i, Math.min(i + m, n), Math.min(i + (m << 1), n));
    }
    actions.push({type: "swap"});
    array = array0, array0 = array1, array1 = array;
  }

  function merge(left, right, end) {
    actions.push({type: "merge", left: left, end: end});
    for (var i0 = left, i1 = right, j = left; j < end; ++j) {
      if (i0 < right && (i1 >= end || array0[i0] <= array0[i1])) {
        array1[j] = array0[i0];
        actions.push({type: "copy", "0": i0++, "1": j});
      } else {
        array1[j] = array0[i1];
        actions.push({type: "copy", "0": i1++, "1": j});
      }
    }
  }

  return actions;
}

</script>

## thumbnail.png

      
    Raw
  

              thumbnail.png
	<!DOCTYPE html>
	<meta charset="utf-8">
	<style>

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

	.line--inactive {
	stroke: #ddd;
	stroke-width: 1px;
	}

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

	var n = 200,
	array = d3.shuffle(d3.range(n)),
	actions = mergesort(array.slice()).reverse();

	var margin = {top: 180, right: 40, bottom: 180, left: 40},
	width = 960 - margin.left - margin.right,
	height = 500 - margin.top - margin.bottom;

	var y = d3.scale.ordinal()
	.domain([1, 0])
	.rangeRoundBands([height, 0], .3);

	var x = d3.scale.ordinal()
	.domain(d3.range(n))
	.rangePoints([0, width]);

	var a = d3.scale.linear()
	.domain([0, n - 1])
	.range([-45, 45]);

	var svg = d3.select("body").append("svg")
	.attr("width", width + margin.left + margin.right)
	.attr("height", height + margin.top + margin.bottom)
	.append("g")
	.attr("transform", "translate(" + margin.left + "," + margin.top + ")");

	var line = svg.append("g")
	.attr("class", "line")
	.selectAll("line")
	.data(array.map(function(v, i) {
	return {
	value: v,
	index: i,
	array: 0
	};
	}))
	.enter().append("line")
	.attr("transform", transform)
	.attr("y2", -y.rangeBand());

	var line0 = line[0],
	line1 = new Array(n);

	var transition = d3.transition()
	.duration(75)
	.each("start", function start() {
	var action = actions.pop();
	switch (action.type) {
	case "merge": {
	d3.selectAll(line0).attr("class", function(d, i) { return action.left <= i && i < action.end ? null : "line--inactive"; });
	break;
	}
	case "copy": {
	var i = action[0],
	j = action[1],
	e = line1[j] = line0[i],
	d = e.__data__;
	d.index = j;
	d.array = (d.array + 1) & 1;
	transition.each(function() { d3.select(e).transition().attr("transform", transform); });
	break;
	}
	case "swap": {
	var t = line0;
	line0 = line1;
	line1 = t;
	break;
	}
	}
	if (actions.length) transition = transition.transition().each("start", start);
	});

	function transform(d) {
	return "translate(" + x(d.index) + "," + y(d.array) + ")rotate(" + a(d.value) + ")";
	}

	function mergesort(array) {
	var actions = [],
	n = array.length,
	array0 = array,
	array1 = new Array(n);

	for (var m = 1; m < n; m <<= 1) {
	for (var i = 0; i < n; i += (m << 1)) {
	merge(i, Math.min(i + m, n), Math.min(i + (m << 1), n));
	}
	actions.push({type: "swap"});
	array = array0, array0 = array1, array1 = array;
	}

	function merge(left, right, end) {
	actions.push({type: "merge", left: left, end: end});
	for (var i0 = left, i1 = right, j = left; j < end; ++j) {
	if (i0 < right && (i1 >= end \|\| array0[i0] <= array0[i1])) {
	array1[j] = array0[i0];
	actions.push({type: "copy", "0": i0++, "1": j});
	} else {
	array1[j] = array0[i1];
	actions.push({type: "copy", "0": i1++, "1": j});
	}
	}
	}

	return actions;
	}

	</script>