partitsort(field A, int l, int r) {
for i:= 0 to ((r-l+1) div 2) do {
q:= partition(A, l+i, r-i, 0);
do parallel {
partition(A, l+i, q, 1);
} and {
partition(A, q+1, r-i, 2);
}
}
}
int partition(field A, int l, int r, int k) {
if (l < r) then {
q:= (r-l+1)/2;
for i:= l+q to r do parallel {
if (A[i-q] > A[i]) then {
exchange(A[i-q], A[i]);
}
}
if (k==0) then { return r-q; }
else if (k==1) { partition(A, l , r-q, k); }
else if (k==2) { partition(A, r-q+1, r , k); }
}
return -1;
}
|