bitonicsort(field A, int l, int r) {
  for m:= 2 to r-l+1 step m do {
    asc:= true;
    for i:= l to r step m do parallel {
      bitonicmerge(A, i, i+m-1, asc);
      asc:= not asc;
    }
  }
}
 
bitonicmerge(field A, int l, int r, bool asc) {
  if (l < r) then {
    q:= (l+r) div 2;
    k:= q-l+1;
    for i:= l to q do parallel {
      if ((A[i] > A[i+k]) = asc) then {
        exchange(A[i], A[i+k]);
      }
    }
    do parallel {
      bitonicmerge(A, l, q, asc);
      bitonicmerge(A, q+1, r, asc);
    }
  }
}

bitonicsort(field A, int l, int r) {
  bitonicsort(A, l, r, true, r-l+1);
}

bitonicsort(field A, int l, int r, bool asc, int m) {
  if (m >= 2) then {
    bitonicsort(A, l, r, asc, m div 2);
    merge(A, l, r, asc, m);
  }
}

merge(field A, int l, int r, bool asc, int m) {
  if (l < r) then {
    bitonicmerge(A, l, l+m-1, asc);
    merge(A, l+m, r, not asc, m);
  }
}
 
bitonicmerge(field A, int l, int r, bool asc) {
  if (l < r) then {
    q:= (l+r) div 2;
    comp(A, l, q, q-l+1, asc);
    do parallel {
      bitonicmerge(A, l, q, asc);
      bitonicmerge(A, q+1, r, asc);
    }
  }
}

comp(field A, int l, int r, int k, bool asc) {
  if (l < r) then {
    q:= (l+r) div 2;
    do parallel {
      comp(A, l  , q, k, asc);
      comp(A, q+1, r, k, asc);
    }
  } else {
    if ((A[l] > A[l+k]) = asc) then {
      exchange(A[l], A[l+k]);
    }
  }
}