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);
        // One barrier for the whole sort: all workers await between phases.
        // (Previous draft declared CyclicBarrier but used CountDownLatch per phase —
        // unused barrier confused craft. Prefer one consistent primitive.)
        CyclicBarrier barrier = new CyclicBarrier(numThreads + 1); // workers + main

        for (int t = 0; t < numThreads; t++) {
            final int tid = t;
            pool.execute(() -> {
                try {
                    for (int phase = 0; phase < n; phase++) {
                        int start = phase % 2; // 0 = even, 1 = odd
                        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; }
                        }
                        barrier.await(); // phase k complete before k+1 reads
                    }
                } catch (Exception e) { throw new RuntimeException(e); }
            });
        }
        for (int phase = 0; phase < n; phase++) barrier.await(); // main marches phases
        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 CyclicBarrier is the sole phase sync (no unused latch).

A concrete sort, traced phase by phase

Sort [5, 2, 4, 1] (n = 4). Each phase compare-swaps its disjoint pairs, then the barrier ends the phase:

Phase	Type	Pairs compared	Array after phase
0	even	(0,1): 5>2 swap · (2,3): 4>1 swap	[2, 5, 1, 4]
1	odd	(1,2): 5>1 swap	[2, 1, 5, 4]
2	even	(0,1): 2>1 swap · (2,3): 5>4 swap	[1, 2, 4, 5]
3	odd	(1,2): 2<4 no swap	[1, 2, 4, 5] — sorted

Four phases (n = 4) suffice; the last odd phase confirms no element is out of place. Notice each array snapshot is the state after the barrier, i.e. after every swap of that phase has completed.

The barrier does double duty: ordering and visibility

It is tempting to think the barrier only orders the phases (phase k finishes before phase k+1 starts). It does more: crossing CyclicBarrier.await() establishes a happens-before edge (JLS §17.4.5). Per the CyclicBarrier javadoc, actions in a thread prior to its await() happen-before the barrier action, which in turn happens-before actions following await() in the other threads. So the swaps a worker writes in phase k are guaranteed visible to whichever thread reads those indices in phase k+1 — which is exactly why the plain int[] needs no volatile and no lock even though different threads read what others wrote. Without that happens-before edge, a reader in phase k+1 could legally observe a stale, pre-swap value even after the swap "finished" in wall-clock time.

Equivalent latch form (if you prefer): one CountDownLatch(numThreads) per phase, main awaits — but then do not also allocate an unused CyclicBarrier.

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.

When NOT to use odd-even sort as a production sorter

• General-purpose sorting — use library sort (n log n); odd-even is a teaching/parallel-compare network pattern.
• Need stable sort with complex objects — wrong tool.

Defending the O(n²): odd-even vs parallel merge sort vs bitonic

A panel will not let “it’s parallel” excuse the quadratic work — parallelism divides your work by the core count, it does not change the algorithm’s total work, and total work is what you pay for. Odd-even transposition does n phases × up to n/2 compares = n²/2 comparisons, O(n²) work, with a parallel depth (span) of n phases. Line it up against the two alternatives you will be asked to compare:

Sorter	Total work (compares)	Parallel depth / span	Communication	Data-oblivious?
Odd-even transposition	O(n²) ≈ n²/2	O(n) phases	nearest-neighbour only	Yes (fixed schedule)
Parallel merge sort	O(n log n) — work-optimal	O(log²n) with parallel merge	global (merge across halves)	No (branches on data)
Bitonic sort (network)	O(n log²n)	O(log²n) stages	butterfly / long-range	Yes (fixed schedule)

Put a number on the gap. The work ratio of odd-even to merge sort is (n²/2) / (n·log₂n) = n / (2·log₂n):

• n = 64: 64/(2·6) ≈ 5.3× more compares than merge sort.
• n = 1024: 1024/(2·10) ≈ 51×.
• n = 10⁶: 10⁶/(2·20) ≈ 25,000×.

Because both algorithms’ work is divided by the same p cores, that ratio is not recovered by throwing cores at it: with 8 cores, odd-even at n=1024 still does ~51× the work merge sort does. So on any general CPU, odd-even loses, and loses worse as n grows.

So when does odd-even actually win? Only where its two structural advantages — a fixed, data-independent schedule and nearest-neighbour-only communication — are worth more than the extra compares:

• vs parallel merge sort: merge sort is work-optimal but branches on data (divergent control flow) and needs global data movement to merge halves. On a SIMD lane or a 1-D systolic/mesh array where branching stalls the whole warp and only neighbour links are cheap, odd-even’s oblivious, local-only pattern can beat merge sort for small n, despite doing more compares — the compares are free, the communication merge sort needs is not.
• vs bitonic sort: this is the sharper comparison, because bitonic is also an oblivious network but has strictly less work (O(n log²n)) and less depth (O(log²n)) than odd-even’s O(n²)/O(n). So for large n on a GPU, bitonic dominates outright. Odd-even’s one remaining edge over bitonic is communication topology: bitonic needs long-range butterfly exchanges, while odd-even only ever talks to neighbours. On hardware where only neighbour communication is cheap (a linear array, a wavefront) and n is small, odd-even’s locality can still win; everywhere else, prefer bitonic.

The honest one-liner for a panel: “Odd-even is the right choice only when the schedule must be data-oblivious and communication must be nearest-neighbour, and n is small enough that O(n²) compares are cheaper than the global data movement the alternatives need. On a random-access machine, parallel merge sort (work-optimal) or bitonic (fewer, oblivious rounds) wins — the crossover is immediate, ~5× more work already at n=64.”

Interviewer follow-ups & drills

1. Why barrier between odd/even phases? Without it, concurrent swaps race and corrupt order.
2. Failure: missing fence → data race; hang if one thread skips barrier.
3. Drill: re-run the traced [5,2,4,1] sort above by hand, then answer: what publishes each phase's swaps to the next phase's readers? (The await() happens-before edge — no volatile needed.)

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.