文系が学ぶコンピューターサイエンス：第２回【クイックソート】 ref: http://qiita.com/timakin/items/b553b65de22e2bd4baa7

file0.txt

1 2 3 4 5 6
が正解なら、
6 5 4 3 2 1
のときが最悪。
一個一個前に持ってこなきゃいけない。

file1.txt

function Sort() {}
Sort.prototype = {
  swap: function(items, lower, upper) {
    var temp = items[lower];
    items[lower] = items[upper];
    items[upper] = temp;
  },
  // クイックソートの基準値を返す関数
  partition: function (data, bottom, top) {
    var pivot = data[bottom];
    // 両端の値を設定。
    var lower = bottom;
    var upper = top;
    while (lower <= upper) {
      while (data[lower] < pivot) {
        lower++;
      }
      while (data[upper] > pivot) {
        upper--;
      }
      if (lower <= upper) {
        this.swap(data, lower, upper);
        lower++;
        upper--;
      }
    }
    return lower;
  },
  quick: function (data, bottom, top) {
    var self = this;
    if (bottom >= top) { return; }
    // 基準値の周りで並び替えが終わったらそのサイクルは終了。
    // ここからがいわゆるpartition（基準点）を作る処理
    // 便宜上左端の値を基準値にしている。
    var index = self.partition(data, bottom, top);
    self.quick(data, bottom, index-1);
    self.quick(data, index, top);
    return data;
  }
}

sort.js

function Sort() {}
Sort.prototype = {
  swap: function(items, lower, upper) {
    var temp = items[lower];
    items[lower] = items[upper];
    items[upper] = temp;
  },
  // クイックソートの基準値を返す関数
  partition: function (data, bottom, top) {
    var pivot = data[bottom];
    // 両端の値を設定。
    var lower = bottom;
    var upper = top;
    while (lower <= upper) {
      while (data[lower] < pivot) {
        lower++;
      }
      while (data[upper] > pivot) {
        upper--;
      }
      if (lower <= upper) {
        this.swap(data, lower, upper);
        lower++;
        upper--;
      }
    }
    return lower;
  },
  quick: function (data, bottom, top) {
    var self = this;
    if (bottom >= top) { return; }
    // 基準値の周りで並び替えが終わったらそのサイクルは終了。
    // ここからがいわゆるpartition（基準点）を作る処理
    // 便宜上左端の値を基準値にしている。
    var index = self.partition(data, bottom, top);
    self.quick(data, bottom, index-1);
    self.quick(data, index, top);
    return data;
  }
}