「いやなブログ - JavaScript でソートアルゴリズムを可視化」より。何も考えずに再帰処理のクイックソートの様子を逐次描画しようとするとこうなります。

function quickSort(data, begin, end, log) {
  if (begin >= end) return data;

  var pivotPos = begin;
  var pivot = data[pivotPos];

  for (var i = begin + 1; i < end; i++) {
    if (data[i] < pivot) {
      var temp = data[i];
      data[i] = data[pivotPos + 1];
      data[pivotPos + 1] = data[pivotPos];
      data[pivotPos] = temp;
      pivotPos++;
    }
  }

  log(data);

  quickSort(data, begin, pivotPos, log);
  quickSort(data, pivotPos + 1, end, log);
  return data;
}

var array = [9, 5, 7, 3, 2, 4, 0, 1, 6, 8];
quickSort(array, 0, array.length, print);
// 5,7,3,2,4,0,1,6,8,9
// 3,2,4,0,1,5,7,6,8,9
// ...
// 0,1,2,3,4,5,6,7,8,9

しかし、ブラウザ上でアニメーション表示するためには、setTimeout などのタイマーを使う必要があります。ところが、タイマーを使って処理を分けると、その処理が終わった後で元の処理に戻ることができません。上のクイックソートでいうと、データの前半を並び替えた後、戻って後半を並び替えないといけないため、そのままではアニメーション表示ができないのです。

ではどうするか。戻らなくてはならないのが問題ならば、戻らなければいいのです。呼び出し先から戻って続きの処理をやるのではなく、続きの処理 (継続) も呼び出し先に丸投げしてしまいましょう。JavaScript ではクロージャが使えるので、続きの処理をまとめたクロージャを引数として渡すことができます。このような書き方を継続渡しスタイル (CPS, continuation passing style) というそうです。「ヒビノキロク - Javascriptで継続渡し」を参考に上のクイックソートを継続渡しスタイルに書き換えてみます。

function quickSortCPS(data, begin, end, log, cont) {
  if (begin >= end) return cont(data);

  var pivotPos = begin;
  var pivot = data[pivotPos];

  for (var i = begin + 1; i < end; i++) {
    if (data[i] < pivot) {
      var temp = data[i];
      data[i] = data[pivotPos + 1];
      data[pivotPos + 1] = data[pivotPos];
      data[pivotPos] = temp;
      pivotPos++;
    }
  }

  log(data);

  return quickSortCPS(data, begin, pivotPos, log,
    function (partiallySortedData) {
      return quickSortCPS(partiallySortedData, pivotPos + 1, end, log,
        function (entirelySortedData) {
          return cont(entirelySortedData);
        });
    });
}

function nop() {}
quickSort(array, 0, array.length, nop, print);
// 0,1,2,3,4,5,6,7,8,9

return 文に式が指定されていますが、この返り値は意味を持ちません。処理結果は関数呼び出しの返り値として受け取るのではなく、継続として渡したクロージャが引数として受け取ります。

さて、ここまで来れば後は簡単です。返す値に意味がない、すなわち戻る必要がなくなったのですから、大手を振ってタイマーが使えます。Gecko では setTimeout の引数として関数実行時の引数も渡せるので、以下のように書き換えられます。

function quickSortCPSWithTimer(data, begin, end, interval, log, cont) {
  ...

  return setTimeout(quickSortCPSWithTimer, interval,
    data, begin, pivotPos, interval, log,
    function (partiallySortedData) {
      return setTimeout(quickSortCPSWithTimer, interval,
        partiallySortedData, pivotPos + 1, end, interval, log,
        function (entirelySortedData) {
          return cont(entirelySortedData);
        });
    });
}

function plot(data) {
  ...
}
quickSortCPSWithTimer(array, 0, array.length, 20, plot, nop);

これで 20 ミリ秒ごとにソート途中のデータがプロットされることになります。実際は IE だと setTimeout で引数を渡せないので、Gecko の setTimeout と同じ動作をする関数 doLater を使います。

function doLater(func, interval) {
  var args = Array.prototype.slice.call(arguments, 2);
  return setTimeout(function () { func.apply(this, args); }, interval);
}

以上をまとめた