Merge Sort

View full screen.

Robert Sedgewick designed these elegant visualizations of a bottom-up merge sort algorithm, published in Algorithms in C (1998). Seven sequential passes to sort a 200-element array are shown, with array values encoded using angle. The design, reminiscent of wind gusting over tall grasses, allows rapid perception of sorted sub-arrays. For comparison, see the same visualization applied to quicksort.

Next: Index Charts

Source

<html>
  <head>
    <title>Merge Sort</title>
    <link type="text/css" rel="stylesheet" href="ex.css?3.2"/>
    <script type="text/javascript" src="../protovis-r3.2.js"></script>
    <script type="text/javascript" src="sort.js"></script>
    <style type="text/css">

#fig {
  width: 820px;
  height: 370px;
}

    </style>
  </head>
  <body><div id="center"><div id="fig">
    <script type="text/javascript+protovis">

/* Sizing and scales. */
var w = 760,
    h = 20;

/* The root panel. */
var vis = new pv.Panel()
    .data(mergesort(data).slice(2))
    .width(w)
    .height(h)
    .margin(30)
    .bottom(0);

/* The wedge with angle encoding. A line would also work. */
vis.add(pv.Panel)
    .data(function(d) d)
    .left(pv.Scale.linear(data, pv.index).range(0, w).by(pv.index))
  .add(pv.Wedge)
    .outerRadius(30)
    .bottom(0)
    .angle(0)
    .startAngle(pv.Scale.linear().range(-Math.PI / 2 - 1, -Math.PI / 2 + 1))
    .strokeStyle("black");

vis.render();

    </script>
  </div></div></body>
</html>

Data

/* A 200-element array of random numbers in [0, 1]. */
var data = pv.range(200).map(Math.random);

/**
 * Sorts the specified array using bottom-up mergesort, returning an array of
 * arrays representing the state of the specified array after sequential passes.
 * The first pass is performed at size = 2.
 */
function mergesort(array) {
  var passes = [array.slice()], size = 2;
  for (; size < array.length; size <<= 1) {
    for (var i = 0; i < array.length;) {
      merge(array, i, i + (size >> 1), i += size);
    }
    passes.push(array.slice());
  }
  merge(array, 0, size >> 1, array.length);
  passes.push(array.slice());

  /** Merges two adjacent sorted arrays in-place. */
  function merge(array, start, middle, end) {
    for (; start < middle; start++) {
      if (array[start] > array[middle]) {
        var v = array[start];
        array[start] = array[middle];
        insert(array, middle, end, v);
      }
    }
  }

  /** Inserts the value v into the subarray specified by start and end. */
  function insert(array, 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;
}