1// quicksort
2
3function sort_quick(sort, left, right) {
4  if (arguments.length == 1) {
5    left = 0;
6    right = sort.size - 1;
7  }
8  if (left < right) {
9    var pivot = left + Math.floor(Math.random()*(right-left));
10    //var pivot = Math.floor(left + (right-left)/2);
11    partition(sort, left, right, pivot);
12  }
13}
14
15function partition(sort, left, right, pivot) {
16  sort.swap(pivot, right);
17  sort.add_work(function(){partition_step(sort, left, right, pivot, left, left);});
18}
19
20function partition_step(sort, left, right, pivot, i, j) {
21  if (i < right) {
22    if (sort.compare(i, right) <= 0) {
23      sort.swap(i, j);
24      j++;
25    }
26    i++;
27    sort.add_work(function(){partition_step(sort, left, right, pivot, i, j)});
28  } else {
29    sort.swap(j, right);
30    sort.add_work(function(){sort_quick(sort, left, j-1)});
31    sort.add_work(function(){sort_quick(sort, j+1, right)});
32  }
33}
34
35