Problem 6 Odd-Even sort

Parallelism without locks — because each phase touches disjoint pairs

Odd-even transposition sort runs in phases. An even phase compares-and-swaps pairs (0,1),(2,3),(4,5)…; an odd phase compares (1,2),(3,4)…. The key property: within a single phase the pairs share no index, so every compare-swap is independent and can run on a different thread with no lock at all — the data they touch is disjoint. The only synchronization needed is a barrier at the end of each phase, so all swaps of phase k finish before phase k+1 reads the array. After n phases the array is sorted.

The earlier version's bug came from a partition formula that handed two threads the same start index (begin=2 for both), so they compare-swapped the same pair concurrently — a genuine data race, presented as correct. The fix is a strided assignment that provably gives each thread disjoint pairs.

Correct Java

import java.util.concurrent.*;

class OddEvenSort {
    void sort(int[] a, int numThreads) throws Exception {
        int n = a.length;
        ExecutorService pool = Executors.newFixedThreadPool(numThreads);
        CyclicBarrier barrier = new CyclicBarrier(numThreads);

        for (int phase = 0; phase < n; phase++) {
            final int start = phase % 2;                 // 0 = even, 1 = odd
            CountDownLatch done = new CountDownLatch(numThreads);
            for (int t = 0; t < numThreads; t++) {
                final int tid = t;
                pool.execute(() -> {
                    // strided, DISJOINT pairs: i = start + 2*tid, then +2*numThreads
                    for (int i = start + 2*tid; i + 1 < n; i += 2*numThreads) {
                        if (a[i] > a[i+1]) { int tmp=a[i]; a[i]=a[i+1]; a[i+1]=tmp; }
                    }
                    done.countDown();
                });
            }
            done.await();                                 // barrier: phase k completes before k+1
        }
        pool.shutdown();
    }
}

Because thread tid only ever touches indices start + 2·tid + 2k·numThreads, no two threads share a pair — so the swaps need no lock. The per-phase latch is the barrier.

Correct Go

func oddEvenSort(a []int, workers int) {
    n := len(a)
    for phase := 0; phase < n; phase++ {
        start := phase % 2
        var wg sync.WaitGroup
        for t := 0; t < workers; t++ {
            wg.Add(1)
            go func(tid int) {
                defer wg.Done()
                for i := start + 2*tid; i+1 < n; i += 2 * workers {
                    if a[i] > a[i+1] { a[i], a[i+1] = a[i+1], a[i] }
                }
            }(t)
        }
        wg.Wait() // barrier between phases
    }
}

Pitfalls

• Overlapping pairs = data race. Any partitioning that can assign two threads the same i is wrong, even if it "usually" produces a sorted result. The strided formula guarantees disjointness.
• You truly need the barrier: without it, a thread in phase k+1 could read an element another thread is still swapping in phase k.
• This is great for teaching data-parallelism but is O(n²) work — not a production sort; it shines on SIMD/mesh hardware, not a 4-core CPU.

Takeaways

• Disjoint pairs per phase mean the compare-swaps are lock-free; only a per-phase barrier is required.
• Assign strided indices (start + 2·tid, step 2·numThreads) to guarantee disjointness.
• Correctness of a parallel algorithm is about the access pattern, not whether a test run happened to pass.

---

Re-authored for correctness for this guide (the prior version assigned two threads the same pair — a data race shown as correct). Odd-even transposition sort (Habermann, 1972). See also: Barriers, Critical Section & Race Condition.

I'm working on the problem **Problem 6 Odd-Even sort** (Concurrency). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Explain the optimal approach to **Problem 6 Odd-Even sort** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

I'll paste my solution to **Problem 6 Odd-Even sort**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Give me 2 problems that use the SAME underlying pattern as **Problem 6 Odd-Even sort**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.