/* pairsort.js */

function pairsort(a) {

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

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--) {
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);
}

pairsort0(0, a.length);

records.nswap = nswap;
records.ncompare = ncompare;
records.swaps = recswaps;

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;

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