Batcher's odd-even-merge sort

Question

Hi I have a question about Batcher's odd-even-merge sort. I have the 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 provide some comments about the code's function:
It's divided into phases indexed by variable p the last phase is when p==n is batchers odd-even-merge the next-to-phase is when p==n/2 is odd-even-merge with the first stage and all comparators that cross n/2 eliminated the third-to-last phase is when p==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.

Results are:

3
3
4
4
5
2
6

What have I missed?
What is wrong?

Compatible

sorry Pieter lesson on proper indenting? – Compatible

Try formatting your code correctly - it makes it easier to spot mistakes – Enchanting

it is formatted as it is possible so any ideas? – Compatible

Is this code from the Sledgewick R. book. Program 11.4 presents a non-recursive odd-even-merge sort, but the constructed sorting network is not identical to Figure 11.7. Have you tested your network for correctness? – Paludal

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.

Amalberga

Answer 2

     '* this assumes array() is globally available
     '* Batcher Odd-even mergesort is limited to power of 2 size arrays. it will
     '* malfunction in any other case. coded from c source by codeguy (qb64.net)
     SUB batcherOddEvenMergeSort (Start&, Finish&)
     IF (Finish& > 1) THEN
         m& = (Finish&) \ 2
         batcherOddEvenMergeSort Start&, m&
         batcherOddEvenMergeSort Start& + m&, m&
         batcheroddEvenMerge Start&, Finish&, 1
     END IF
     END SUB

     SUB batcheroddEvenMerge (Start&, Finish&, r&)
     m& = r& * 2
     IF m& > 0 AND m& < Finish& THEN
        batcheroddEvenMerge Start&, Finish&, m&
        batcheroddEvenMerge Start& + r&, Finish&, m&
        i& = Start& + r&
        DO
           IF i& + m& > Start& + Finish& THEN
              EXIT DO
           ELSE
              IF array(i&) > array(i& + r&) THEN
                swap array(i&), array(i& + r&)
             END IF
             i& = i& + m&
           END IF
        LOOP
     ELSE
        IF array(Start&) > array(Start& + r&) THEN
           swap array(Start&), array(Start& + r&)
        END IF
    END IF
    END SUB
    '* this is adapted from c code and works correctly

Titoism

Answer 3

This is a fixed subroutine.

void sort(int n)
{
  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++) // wrong line
        for (int i = 0; i < k; i++)
          if ((i + j)/(p + p) == (i + j + k)/(p + p))
            printf("%2i cmp %2i\n", i + j, i + j + k);
}

Hyderabad

Answer 4

//This is a fixed subroutine
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) < p && a[l + j + i] > a[l + j + i + k])
                        exch(a, l + j + i, l + j + i + k);
}

Borreri

Like the answer from W K Park, this could do with an explanation of how the code was changed to fix the problem and why the previous code caused a problem. – Ellipticity