Skip to content

Instantly share code, notes, and snippets.

@mbostock
Last active February 9, 2016 00:27
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save mbostock/1243323 to your computer and use it in GitHub Desktop.
Merge Sort
license: gpl-3.0

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.

<!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 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>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment