Mergesort IV

forked from mbostock's block: Mergesort IV

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

body {
  background: #000;
}

.line {
  fill: none;
  stroke: #000;
  stroke-width: 6px;
  stroke-linecap: round;
  stroke-linejoin: round;
}

.line-halo {
  stroke-linecap: butt;
  stroke-width: 8px;
}

</style>
<body>
<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.5.5/d3.min.js"></script>
<script src="cubehelix.js"></script>
<script>

var n = 100,
    array = d3.shuffle(d3.range(n)),
    arrays = mergesort(array);
    arrays = expand(arrays,4);

var elements = d3.range(n).map(function(i) { return {value: i, indexes: []}; });

var color = d3.scale.cubehelix()
    .domain([0, n / 2, n - 1])
    .range([d3.hsl(-40, 1, .4), d3.hsl(60, 1, 1), d3.hsl(160, 1, .4)]);

arrays.forEach(function(array, t) {
  array.forEach(function(value, i) {
    elements[value].indexes.push({time: t, index: i});
  });
});

var margin = {top: 20, right: 20, bottom: 20, left: 20},
    strokeWidth = 6,
    width = 960 - margin.left - margin.right,
    height = 700 - margin.top - margin.bottom;

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

var y = d3.scale.ordinal()
    .domain(d3.range(arrays.length))
    .rangePoints([0, height]);

var line = d3.svg.line()
    .interpolate("basis")
    .x(function(d) { return x(d.index); })
    .y(function(d) { return y(d.time); });

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 + ")");

svg.append("g")
    .attr("class", "line")
  .selectAll("path")
    .data(elements)
  .enter().append("path")
    .style("stroke", function(d) { return color(d.value); })
    .attr("d", function(d) { return line(d.indexes); })
  .select(function() { return this.parentNode.insertBefore(this.cloneNode(false), this); })
    .attr("class", "line-halo")
    .style("stroke", null);

function expand(array,num){
    var m=[];
    for (var i = 1; i<array.length;i++){
        for (var j = 1; j<num;j++){
            m.push(array[i]);
        }
    }
return m;
}

function mergesort(array) {
  var arrays = [array.slice()],
      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));
    }
    arrays.push(array1.slice());
    array = array0, array0 = array1, array1 = array;
  }

function merge(left, right, end) {
    for (var i0 = left, i1 = right, j = left; j < end; ++j) {
      array1[j] = array0[i0 < right && (i1 >= end || array0[i0] <= array0[i1]) ? i0++ : i1++];
    }
  }

return arrays;
}

d3.select(self.frameElement).style("height", height + margin.top + margin.bottom + "px");

</script>

https://cdnjs.cloudflare.com/ajax/libs/d3/3.5.5/d3.min.js