function quicksort(arr) {
  var N = arr.length,
      actions = [];

  //recursive sort call with n*log(n) average case complexity
  function sort(a, lo, hi) {
    if(lo >= hi) return;
    var j = partition(a, lo, hi);
    sort(a, lo, j-1);
    sort(a, j+1, hi);
  }

  function partition(a, lo, hi) {
    var i = lo,
        j = hi+1,
        v = a[lo]; // partition value

    while(1) {
      while(a[++i] <= v) if(i == hi) break;
      while(a[--j] >= v) if(j == lo) break;
      if(i >= j) break; // indices cross
      swap(a, i, j);
    }

    swap(a, lo, j); //swap partition element into place
    actions.push({type: "partition", pivot: j});
    return j;
  }

  function swap(arr, i, j) {
    var t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
    actions.push({type: "swap", i: i, j: j});
  }

  sort(arr, 0, N-1);

  return actions;
}

// Node or browser?
if (typeof window === 'undefined') {
  module.exports = quicksort;

} else {
  window.quicksort = quicksort;
}