question about Batcher odd-even sort

Question

hi i have question about Batcher's odd-even sort i have following code

public class Batcher{
public static void batchsort(int a[],int l,int r){
  int n=r-l+1;

  for (int p=1;p<n;p+=p)
   for (int k=p;k>0;k/=2)
 for (int j=k%p;j+k<n;j+=(k+k))
   for (int i=0;i<n-j-k;i++)
     if ((j+i)/(p+p)==(j+i+k)/(p+p))
  exch(a,l+j+i,l+j+i+k);
}

public static void main(String[]args){

int a[]=new int[]{2,4,3,4,6,5,3};


batchsort(a,0,a.length-1);

 for (int i=0;i<a.length;i++){
  System.out.println(a[i]);
}

  }
 public static void    exch(int a[],int i,int j){
  int t=a[i];
a[i]=a[j];
a[j]=t;

}
}

i will add some comment about code function it divides into phases indexed by variable p the last phase when p==n is batchers odd-even

merge the next-to-phase when p is n/2 is odd-even merge with the first stage and all comparators that cross n/2 eliminated the third-to-last phase when p is n/4 the odd-even merge with the first two stages and all comparator that cross any multiple of n/4 eliminated and so forth //result is

3
3
4
4
5
2
6

what i missed ? what is wrong?

Answer 1

I don't know the algorithm but you need to compare values in a in batchsort before switching them, e.g.

if ((j + i) / (p + p) == (j + i + k) / (p + p))
{
    if (a[l + j + i] > a[l + j + i + k])
    {
        exch(a, l + j + i, l + j + i + k);
    }
}

or that might be more readable if you use temp variables for the combined indices, e.g.

if ((j + i) / (p + p) == (j + i + k) / (p + p))
{
    int i1 = l + j + i;
    int i2 = l + j + i + k;
    if (a[i1] > a[i2])
    {
        exch(a, i1, i2);
    }
}

but the commenters above are right - this really isn't written very readably at all. You should try to make sure that equal braces have the same indent, that nested for()s have more indent than their containing for, etc., and you should probably pick more descriptive variable names too.