block by mbostock 1243323

Merge Sort

Full Screen

This animation is based on elegant visualizations by Robert Sedgewick, published in Algorithms in C (1998). Seven sequential passes of a bottom-up merge sort algorithm are shown, with array values encoded using angle. The design, reminiscent of wind gusting over tall grasses, allows rapid perception of sorted sub-arrays. Based on an earlier Protovis example.

See also quick sort.

index.html

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

body {
  margin-top: 225px;
}

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

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

// Based on //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>