README.md

## README.md

      
        

          Raw
        
        
          
            
          
          
            
              README.md
            
          
        
      
    
  
    This is an interpretation of mbostock's block: Mergesort I. 

I kept all the passes through the sort visible to be able to compare the steps of the sorting algorithm.

  

  

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

<head>

    <style>
        rect {
            stroke-linecap: round;
            stroke-width: .25px;
            stroke: black;
            fill: #004d00;
        }
    </style>

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

</head>

<body>

    <div id="viz" style="width: 100%;height:100%"></div>

</body>

<script>

    var n = 64,
        duration = 1000;

    var iteration;

    var margin = 40,
        vizDims = document.getElementById('viz').getBoundingClientRect(),
        width = vizDims.width - margin - margin,
        height = vizDims.height - margin - margin;

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

    var svg = d3.select("#viz").append("svg")
        .attr("width", width + margin + margin)
        .attr("height", height + margin + margin)
      .append("g")
        .attr("class", "rows")
        .attr("transform", "translate(" + margin + "," + margin + ")");

    loadRow();

    function loadRow() {

        iteration = 0;

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

        var rowCount = Math.ceil(actions.length/n),
            rectHeight = (height/rowCount) * .3,
            rectWidth = (width/n) * .9;

        d3.select("svg").select("g").selectAll("*").html('').remove()

        var rect = svg.append("g")
            .attr("class", "rect row")
          .selectAll("rect")
            .data(array.map(function(v, i) {
                return {
                    value: v,
                    index: i,
                    id: i,
                    array: 0
                };
            }))
            .enter().append("rect")
                .attr({
                    "class": "row" + iteration,
                    "id": function(d) {return "rect" + iteration + "_" + d.id},
                    "x": 0,
                    "y": x(0),
                    "height": rectHeight,
                    "width": rectWidth
                })
                .style("fill-opacity", function(d) { return d.value/n })
                .transition().duration(duration)
                .attr("x", function(d) {return x(d.index)})

        var row0 = rect[0];

        setTimeout(function() {mergeRows()}, duration * 2);

        function mergeRows() {

            var row1 = new Array(n);

            var transition = d3.transition()
                .duration(duration/20)
                .each("start", function start() {
                    var action = actions.pop();
                    if (action[1] === 0) { iteration++; };
                    switch (action.type) {
                        case "copy": {
                            var i = action[0],
                                j = action[1],
                                e = row1[j] = row0[i],
                                d = e.__data__;
                            d.index = j;
                            transition.each(function() {
                                var source = d3.select("#rect" + (iteration - 1) + "_" + d.id)
                                d3.select("svg").select(".row").append("rect")
                                    .attr({
                                        "class": "row" + iteration,
                                        "id": "rect" + iteration + "_" + d.id,
                                        "style": source.attr("style"),
                                        "x": source.attr("x"),
                                        "y": source.attr("y"),
                                        "height": rectHeight,
                                        "width": rectWidth
                                    })
                                    .transition().duration(duration/2)
                                    .attr("x", x(d.index))
                                    .attr("y", iteration * rectHeight * 2 )

                            });
                            break;
                        }
                        case "swap": {
                                var t = row0;
                                row0 = row1;
                                row1 = t;
                                break;
                        }
                    }
                    if (actions.length) {
                        transition = transition.transition().each("start", start);
                    } else {
                        setTimeout(function() { returnRects()}, duration * 2)
                    };

                });

        }

    }

    function returnRects() {

        for (z=1; z<=iteration; z++) {
            var thisRow = d3.selectAll(".row" + z)[0];

            for (i=0; i<thisRow.length; i++) {
                var thisId = d3.select(thisRow[i]).attr("id").split("_")[1];

                d3.select(thisRow[i])
                    .transition().duration(duration * 2)
                    .attr("x", x(thisId))
                    .attr("y", 0)
                    .remove()
            }
        }

        setTimeout(function() {
            d3.selectAll('rect')
                .transition().duration(duration * 2)
                .attr("x", function() {return x(0)})

            setTimeout(function() { loadRow(); }, duration * 2)
        }, duration * 2)

    }

    function mergesort(array) {

        actions = [];
        n = array.length;

        var 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) {
            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>
</html>

## thumbnail.png

      
        

          Raw
        
        
          
            
          
          
            
              thumbnail.png