/* pairsortrep.js */

function pairsortrep(a) {

var records = [], ncompare = 0, nswap = 0, recswaps = [], i;

var bound, iter, lowerbound;

function compare(x, y) {
ncompare++;
return x < y;
}

function swap(i, j) {
var x = a[i];
a[i] = a[j];
a[j] = x;
recswaps[nswap++] = [i,j];
/* it's important to tell you that
these records are later used,
and the assumption is made that
a record [i, j] has i < j. */
}

function pairsort0(start, end) {
var i, j;
for (i=start, j=end-1; i<j; i++,j--) {
if (j-i > bound)
continue;
if (j-i < lowerbound)
continue;
records[records.length] = [i, j];
if (compare(a[j], a[i]))
swap(i, j);
}
j++;
if (j-start > 1)
pairsort0(start, j);
if (end-i > 1)
pairsort0(i, end);
}

iter = 0;

do {
iter++;
bound = Math.ceil((a.length+1)/Math.pow(2, iter-1));
//lowerbound = Math.floor(Math.log(bound/2)/Math.log(2));
lowerbound = Math.floor(Math.pow(Math.log(a.length)/Math.log(2),.5/iter));

ncompare = 0, nswap = 0;
recswaps = [];
records = [];

pairsort0(0, a.length);

records.bound = bound;
records.lowerbound = lowerbound;
records.nswap = nswap;
records.ncompare = ncompare;
records.swaps = recswaps;
records.iter = iter;

var furthestswap = 0;
for (i=0; i<recswaps.length; i++)
if (recswaps[i][1] - recswaps[i][0] > furthestswap)
furthestswap = recswaps[i][1] - recswaps[i][0];

records.furthestswap = furthestswap;

displayarray(a, records, 1);

} while (bound > 3);

return records;
/* allows us to analyze the sort */
}