Skip to content

Instantly share code, notes, and snippets.

@a10k
Created November 28, 2015 08:42
Show Gist options
  • Save a10k/0862fbbc87d165cc0a7b to your computer and use it in GitHub Desktop.
Save a10k/0862fbbc87d165cc0a7b to your computer and use it in GitHub Desktop.
mergesort
<!DOCTYPE html>
<meta charset="utf-8">
<style>
line {
stroke: #002776;
stroke-width: 5px;
}
</style>
<body>
<script src="https://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 = 800,
h = 200;
var n = 100,
index = d3.range(n),
x = d3.scale.ordinal().domain(index).rangePoints([0, w-10]),
a = d3.scale.linear().domain([0, n - 1]).range([20, 180]),
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", function(d) { return h-a(d); })
.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) + ")";
}
// 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