Parallel Sorting

Why Parallel Sorting Matters

Suppose two workers independently sort incoming records. One produces [1,7] and the other [2,8]. Concatenating their answers gives [1,7,2,8], which is not sorted. Parallel sorting needs both independent work and a rule that makes the final global order correct. The challenge is deciding what to split, how intermediate results depend on one another, and how to combine them without losing or duplicating records.

We want a nondecreasing permutation of the input: all original values remain, including duplicates, and no adjacent output pair is inverted. Sorting supports joins, ranking, aggregation, duplicate removal, search indexes, and data shuffles. Its performance depends on comparisons, data movement, memory bandwidth, synchronization, and load balance—not just the number of available workers.

This lesson covers four families: parallel merge sort sorts disjoint runs and merges them; parallel quicksort partitions by pivots and sorts independent partitions; bitonic sort follows a fixed network of compare-exchange pairs; sample sort uses sampled splitters to distribute values into ordered buckets. All four are implemented in each language using the same input and deterministic worker assignments.

The implementations simulate jobs sequentially so that every phase is reproducible. They create no threads. This lets us study correctness and scheduling while distinguishing the printed job waves from measured execution time. In particular, a whole merge or partition job may do many comparisons, whereas one bitonic job always performs one comparator.

Core Concepts and Terminology

For input $a=[a_0,\ldots,a_{n-1}]$, the result b must satisfy both

$$b_i\le b_{i+1}\quad(0\le i\lt n-1),\qquad \operatorname{multiset}(b)=\operatorname{multiset}(a).$$

A multiset counts multiplicities: sorting [2,2,1] must return [1,2,2], not [1,2]. Empty and singleton inputs are already sorted. A stable sort additionally preserves the original order of equal-key records. The programs sort integer keys only; record identity and payload stability are discussed explicitly rather than inferred from indistinguishable integers.

A comparator needs a consistent ordering. Mathematical integer order is a total order. A custom record comparator must satisfy the ordering contract required by the chosen language/library; inconsistent comparisons invalidate the proofs. A compare-exchange puts the smaller/larger value into the specified output slot. It preserves the pair's multiset even when no swap occurs.

Work W counts all primitive operations; span D follows the longest dependency chain with unlimited workers. Ideal parallel time obeys $T_P\ge\max(W/P,D)$; a suitable scheduling model can obtain an $O(W/P+D)$ bound. These statements count elementary work, not arbitrary jobs as equally cheap. A merge of two thousand-item runs costs much more than a comparator on two integers.

A phase reads a completed source state and publishes a completed destination state after a barrier. Within it, job $j$ is assigned to worker $j\bmod P$ and zero-based wave $\lfloor j/P\rfloor$. The program reports $\lceil J/P\rceil$ dispatch waves for J jobs. This is a deterministic grouping, not a measured duration: unequal job sizes require a cost-aware timing model. The selection phase in sample sort has one serial sample-sort job; distribution describes private per-chunk work conceptually, while the simulator assembles buckets sequentially.

The following merge diagram shows why merely parallelizing recursive calls is insufficient. Four small merges can run independently, then two larger merges, then one final merge. In this code each merge is sequential, so the root remains a linear-size bottleneck. Faster parallel merge algorithms must also split the merge itself into independent output ranges. On this worked input, a restricted comparison-only model that ignores all movement gives work $W=16$ and span $D=1+3+6=10$ along a longest dependency path. These comparison costs are separate from dispatch-wave counts and end-to-end runtime.

How Parallel Sorting Works, Step by Step

The runnable programs choose a deliberately simple version of each family. Read all source data for a phase from a stable state, give each job an exclusive destination range or pair of slots, and publish only after the phase finishes. No job relies on another job's partially updated destination.

1. Parallel merge sort: double the run width. Start with singleton runs. For widths $w=1,2,4,\ldots$ while $w\lt n$, job j handles $[\ell,h)$ with $\ell=2wj$, midpoint $m=\min(\ell+w,n)$, and end $h=\min(\ell+2w,n)$. Sequentially merge the two sorted source slices $[\ell,m)$ and $[m,h)$ into the same destination interval. When keys tie, take the left occurrence first. If the right slice is empty, copy the left run. Jobs write disjoint intervals. After the barrier, every run of up to $2w$ entries is sorted; double w and repeat. A production parallel merge can split a large pair of runs into independently writable output pieces using merge-path/co-ranking or suitable divide-and-conquer.

2. Parallel quicksort: partition active ranges. Begin with the whole range if it has at least two entries. At each depth, process disjoint active ranges left to right. Select the key at source index $\lfloor(\ell+h)/2\rfloor$ as pivot. Scan that range into stable less-than, equal-to, and greater-than lists, then write their concatenation back into its exclusive destination range. Only less/greater subranges of length at least two become tasks for the next depth. The equal band is finished; singleton and empty ranges need no tasks. The pivot is an actual element, so the equal band is nonempty and each descendant is smaller. This deterministic pivot gives reproducible traces, not a worst-case balance guarantee. Real parallel partitioning can use flags, prefix scans, and disjoint scatter positions; this implementation partitions each range sequentially.

3. Bitonic sort: build and merge alternating directions. Let m be the next power of two at least n, except that an empty input has no network. Pad with a value larger than every accepted key. For sizes $s=2,4,\ldots,m$, execute strides $d=s/2,s/4,\ldots,1$. For each slot i, its partner is $j=i\mathbin{\mathrm{xor}}d$. Process the pair only when $j\gt i$, so it executes exactly once. When $(i\mathbin{\mathrm{and}}s)=0$, put the smaller key in i; otherwise put the larger key in i. All pairs at one stride are disjoint. Finish the barrier before the next stride. After all strides for a size, its blocks are sorted in alternating ascending/descending directions; at the final size the single block is ascending. Remove only the trailing padding after the entire network finishes.

Why alternate directions? An ascending run followed by a descending run forms a bitonic sequence. A bitonic merge first compares entries half a block apart, pushing smaller values into one half and larger values into the other, then repeats inside both halves. It cannot sort arbitrary unsorted data in one final merge pass: smaller sizes must first construct the required bitonic input shapes. The step diagram below shows just the first stride of the final size, so its output is intentionally not sorted yet.

4. Sample sort: choose splitters, distribute, then sort buckets. For $n\ge2$, choose $B=\min(P,n)$ buckets and $S=\min(n,2B)$ sample positions $\lfloor in/S\rfloor$ for $0\le i\lt S$. Sort those sampled keys with the same stable local merge helper. Choose splitter j from sorted sample position $\lfloor jS/B\rfloor$ for $1\le j\lt B$. The positions are deterministic and evenly spaced in the input; this is a teaching sample-sort variant, not a proof of balanced buckets or a complete PSRS algorithm.

Assign each key to the upper-bound bucket: its index is the number of splitters less than or equal to that key, implemented by binary search. With one splitter t, the buckets are $x\lt t$ and $x\ge t$. With repeated splitters some buckets may be empty; every key still has one destination. Split the input into B contiguous chunks, classify each chunk, assemble buckets in chunk order, and publish their concatenation. Sort each bucket independently with local merge sort, then concatenate in bucket order. The bucket ranges guarantee global order, unlike arbitrary sorted runs. In a real parallel scatter, use private per-chunk bucket counts, prefix offsets, and disjoint writes; the shared append operations in this sequential simulator must not be copied directly into concurrent code.

The flowchart shows the bitonic core's nested loops and barriers; merge, quick, and sample phases follow the separate procedures above. All four complete algorithms appear in each code panel.

flowchart TD
    A["Validate keys, size, worker count"] --> B{"Fewer than two keys?"}
    B -->|Yes| C["Return input copy"]
    B -->|No| D["Pad to power of two; set size to 2"]
    D --> E["Set stride to size divided by 2"]
    E --> F["Build XOR pairs; assign workers and waves"]
    F --> G["Read old slots; compare in size-dependent direction"]
    G --> H["Barrier; publish complete next state"]
    H --> I{"More strides in this size?"}
    I -->|Yes| J["Halve stride"]
    J --> F
    I -->|No| K{"Larger size needed?"}
    K -->|Yes| L["Double size"]
    L --> E
    K -->|No| M["Trim trailing padding; return sorted keys"]

Worked Example with a Full Trace

Use the shared input [7,2,5,2,9,1,8,3] and two workers. Every final answer must be [1,2,2,3,5,7,8,9]. The duplicate 2 must remain twice. The bitonic diagram records every stage; the prose traces the other three families, and the expected stdout below includes every job and all four complete traces.

Merge trace. Width 1 merges four pairs, producing [2,7,2,5,1,9,3,8] with comparison counts 1, 1, 1, 1. Jobs 0/1 use workers 0/1 in wave 0, and jobs 2/3 use workers 0/1 in wave 1. Width 2 produces [2,2,5,7,1,3,8,9] with 3 comparisons in each of its two jobs, both in wave 0. Width 4 produces [1,2,2,3,5,7,8,9] with 6 comparisons in its single final job. Total: 16 key comparisons and 4 dispatch waves; the waves have unequal work.

Quick trace. At depth 0, range $[0,8)$ selects source index 4, pivot 9. Less/equal/greater sizes are $[7,1,0]$, so the state becomes [7,2,5,2,1,8,3,9] with 9 key comparisons. At depth 1, range $[0,7)$ selects pivot 2 and sizes $[1,2,4]$, yielding [1,2,2,7,5,8,3,9] with 13 comparisons. At depth 2, range $[3,7)$ selects pivot 8 and sizes $[3,1,0]$, yielding [1,2,2,7,5,3,8,9] with 5 comparisons. At depth 3, range $[3,6)$ selects pivot 5 and sizes $[1,1,1]$, yielding the final sorted state with 5 comparisons. All four depths have just one active partition job on worker 0: the chosen pivots expose little task parallelism on this input. Total: 32 key comparisons and 4 dispatch waves.

Bitonic trace. No padding is needed because $n=m=8$. Use s for size and d for stride.

• s=2,d=1: [2,7,5,2,1,9,8,3]; pair directions alternate ASC, DESC, ASC, DESC.
• s=4,d=2: [2,2,5,7,8,9,1,3]; pairs in the first four slots are ASC, the last four DESC.
• s=4,d=1: [2,2,5,7,9,8,3,1]; the two four-key blocks are now ascending and descending.
• s=8,d=4: [2,2,3,1,9,8,5,7]; all pairs are ASC, but neither half is sorted yet.
• s=8,d=2: [2,1,3,2,5,7,9,8]; all pairs are ASC.
• s=8,d=1: [1,2,2,3,5,7,8,9]; the whole block is sorted.

Every stage executes four comparator jobs, including pairs that do not swap. At each stage, jobs 0/1 use workers 0/1 in wave 0 and jobs 2/3 use workers 0/1 in wave 1. Six stages therefore use 24 comparators and 12 unit-cost comparator waves. Four or more workers would need six such waves, one per stage. These unit comparator waves still exclude setup, memory traffic, and barrier overhead.

Sample trace. Two buckets give four sample positions [0,2,4,6], holding [7,5,9,8]. Local sample sorting uses 4 comparisons and gives [5,7,8,9]. The splitter is 8. Chunk $[0,4)$ sends [7,2,5,2] into bucket 0. Chunk $[4,8)$ sends [1,3] into bucket 0 and [9,8] into bucket 1. Classification uses 4 comparisons per chunk. Bucket sizes are $[6,2]$, and the distributed state is [7,2,5,2,1,3,9,8]. Sorting bucket 0 uses 10 comparisons and yields [1,2,2,3,5,7]; bucket 1 uses 1 comparison and yields [8,9]. Concatenation is globally sorted. Total: $4+8+10+1=23$ key comparisons and 3 dispatch waves. The single sample job, distribution jobs, and unequal bucket jobs are not equally expensive.

Observe the distinction: 3 sample-sort dispatch waves do not establish that it is four times faster than 12 bitonic comparator waves. The job definitions differ, and actual performance also depends on communication and data movement.

Implementation in Python, C++, and Java

Each panel is a complete standalone program implementing all four algorithms, in the same order, with the same integer keys, job ordering, phases, key-comparison counts, worker/wave assignments, and output. Python uses 3.9 or later; C++ uses C++17; Java uses Java 8 or later and should be saved as Main.java. Run python3 main.py; compile/run C++ with g++ -std=c++17 -O2 main.cpp -o sorting then ./sorting; compile/run Java with javac Main.java then java Main. There are no dependencies on another code block and no actual worker threads.

The public entry point is sort_all in Python/C++ and sortAll in Java. It validates worker count $1\le P\le16$, length $0\le n\le64$, and integer keys in $[-10^6,10^6]$. Errors are reported in the order PROCESSORS, SIZE, VALUE. Python rejects booleans, floats, strings, and null elements as keys; worker counts must also be exact integers. C++/Java numeric signatures enforce their input types; Java explicitly rejects null keys. The container must be non-null and flat. Valid inputs are copied and left unchanged. Individual sorting helpers assume entry-point validation; call the public entry point to enforce its contract.

Bitonic padding uses PAD=1000001, strictly greater than every accepted key. It is printed as that integer if padding appears in an intermediate state. The sentinel is removed by trimming to the original length only after the final ascending stage. For arbitrary key domains, replace this bounded sentinel with a tagged padding value that compares greater than all real records. Empty and singleton inputs have no phases in every algorithm.

A Job records its range/pair description, key-comparison count, worker, and wave. A Phase records the complete array after its barrier. A Result records the sorted output, phase history, total key comparisons, and the sum of dispatch-wave counts. Sample selection records sampled positions, sorted sample, and splitters while leaving the main array unchanged. Distribution records its bucket sizes and complete bucket concatenation; local bucket merges are summarized by their sorted output and comparison counts, not logged comparison by comparison.

Comparison counts include key comparisons in merge helpers, the actual < pivot and conditional > pivot tests, each bitonic comparator, and sample-sort splitter searches. They exclude loop bounds, index checks, validation, allocations, copies, and printing. A comparator that finds an already ordered pair still counts once. Dispatch-wave totals count scheduling groups of the chosen jobs; only bitonic's one-comparator jobs admit the uniform unit-cost interpretation used above. Private buffers and real barriers would be required before executing these jobs concurrently.

Verification: 5,014 input/worker cases were tested in each language, with 5,007 accepted and 7 rejected. Every accepted case runs all four algorithms, giving 20,028 successful sorts per language. Independent oracles check sorted output, multiplicities, original-window merge states, three-way partition states, every bitonic comparator layer, and sample bucket boundaries/classification, along with 82,683 intermediate phases. Tests cover all permutations through length 6, ternary inputs through length 5, every binary input of length 8, every size 0–64 at several worker counts, duplicates, ordered/reversed inputs, boundary keys, and seeded random data. Full formatted traces agree across languages; sample stdout matches byte for byte. Eight extra Python cases check invalid runtime types. C++ passed address/undefined-behavior sanitizer runs; Java compiled with all lint warnings enabled.

from dataclasses import dataclass

@dataclass
class Job:
    note: str
    comparisons: int
    worker: int
    wave: int

@dataclass
class Phase:
    label: str
    after: list[int]
    jobs: list[Job]
    waves: int

@dataclass
class Result:
    name: str
    output: list[int]
    phases: list[Phase]
    comparisons: int = 0
    waves: int = 0

PAD = 1_000_001  # Greater than every accepted input key.

def array_text(a: list[int]) -> str:
    return "[" + ",".join(map(str, a)) + "]"

def merge_parts(left: list[int], right: list[int]) -> tuple[list[int], int]:
    out: list[int] = []
    i = j = count = 0
    while i < len(left) and j < len(right):
        count += 1
        if left[i] <= right[j]:
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:]); out.extend(right[j:])
    return out, count

def local_sort(values: list[int]) -> tuple[list[int], int]:
    a = list(values)
    width = 1
    count = 0
    while width < len(a):
        out: list[int] = []
        for lo in range(0, len(a), 2 * width):
            piece, c = merge_parts(a[lo:lo + width], a[lo + width:lo + 2 * width])
            out.extend(piece); count += c
        a = out
        width *= 2
    return a, count

def emit(result: Result, label: str, after: list[int],
         notes: list[str], counts: list[int], processors: int) -> None:
    jobs = [Job(note, counts[j], j % processors, j // processors)
            for j, note in enumerate(notes)]
    waves = (len(jobs) + processors - 1) // processors
    result.phases.append(Phase(label, list(after), jobs, waves))
    result.comparisons += sum(counts)
    result.waves += waves

def merge_sort(values: list[int], p: int) -> Result:
    a = list(values); r = Result("merge", [], [])
    width = 1
    while width < len(a):
        out: list[int] = []; notes: list[str] = []; counts: list[int] = []
        for lo in range(0, len(a), 2 * width):
            mid, hi = min(lo + width, len(a)), min(lo + 2 * width, len(a))
            piece, c = merge_parts(a[lo:mid], a[mid:hi])
            out.extend(piece); counts.append(c)
            notes.append(f"range=[{lo},{hi}) mid={mid}")
        emit(r, f"width={width}", out, notes, counts, p)
        a = out; width *= 2
    r.output = a
    return r

def quick_sort(values: list[int], p: int) -> Result:
    a = list(values); r = Result("quick", [], [])
    tasks = [(0, len(a))] if len(a) > 1 else []
    depth = 0
    while tasks:
        before = a; out = list(a)
        next_tasks: list[tuple[int, int]] = []; notes: list[str] = []; counts: list[int] = []
        for lo, hi in tasks:
            pivot = before[(lo + hi) // 2]
            less: list[int] = []; equal: list[int] = []; greater: list[int] = []; c = 0
            for x in before[lo:hi]:
                c += 1
                if x < pivot:
                    less.append(x)
                else:
                    c += 1
                    if x > pivot: greater.append(x)
                    else: equal.append(x)
            out[lo:hi] = less + equal + greater
            left_stop, right_start = lo + len(less), lo + len(less) + len(equal)
            if left_stop - lo > 1: next_tasks.append((lo, left_stop))
            if hi - right_start > 1: next_tasks.append((right_start, hi))
            notes.append(f"range=[{lo},{hi}) pivot={pivot} sizes=" + array_text([len(less),len(equal),len(greater)]))
            counts.append(c)
        emit(r, f"depth={depth}", out, notes, counts, p)
        a = out; tasks = next_tasks; depth += 1
    r.output = a
    return r

def bitonic_sort(values: list[int], p: int) -> Result:
    n = len(values); m = 1
    while m < n: m *= 2
    a = list(values) + [PAD] * (m - n) if n else []
    r = Result("bitonic", [], [])
    size = 2
    while size <= m and n:
        stride = size // 2
        while stride:
            before = a; out = list(a); notes: list[str] = []
            for i in range(m):
                j = i ^ stride
                if j > i:
                    ascending = (i & size) == 0
                    x, y = before[i], before[j]
                    if (x > y if ascending else x < y): x, y = y, x
                    out[i], out[j] = x, y
                    notes.append(f"pair={i},{j} " + ("ASC" if ascending else "DESC"))
            emit(r, f"size={size} stride={stride}", out, notes, [1] * len(notes), p)
            a = out; stride //= 2
        size *= 2
    r.output = a[:n]
    return r

def sample_sort(values: list[int], p: int) -> Result:
    a = list(values); n = len(a); r = Result("sample", [], [])
    if n < 2:
        r.output = a; return r
    b = min(p, n); s = min(n, 2 * b)
    positions = [i * n // s for i in range(s)]
    sample, c = local_sort([a[i] for i in positions])
    splitters = [sample[j * s // b] for j in range(1, b)]
    emit(r, "select splitters=" + array_text(splitters), a,
         ["sample_positions=" + array_text(positions) + " sorted=" + array_text(sample)], [c], p)
    buckets: list[list[int]] = [[] for _ in range(b)]
    notes: list[str] = []; counts: list[int] = []
    for chunk in range(b):
        lo, hi = chunk * n // b, (chunk + 1) * n // b
        c = 0
        for x in a[lo:hi]:
            left, right = 0, len(splitters)
            while left < right:
                mid = (left + right) // 2; c += 1
                if x < splitters[mid]: right = mid
                else: left = mid + 1
            buckets[left].append(x)
        notes.append(f"chunk=[{lo},{hi})"); counts.append(c)
    sizes = list(map(len, buckets))
    out = [x for bucket in buckets for x in bucket]
    emit(r, "distribute sizes=" + array_text(sizes), out, notes, counts, p)
    out = []; notes = []; counts = []; start = 0
    for j, bucket in enumerate(buckets):
        ordered, c = local_sort(bucket)
        out.extend(ordered)
        notes.append(f"bucket={j} range=[{start},{start + len(bucket)})")
        counts.append(c); start += len(bucket)
    emit(r, "sort-buckets", out, notes, counts, p)
    r.output = out
    return r

def sort_all(values: list[int], processors: int) -> list[Result]:
    if type(processors) is not int or not 1 <= processors <= 16:
        raise ValueError("PROCESSORS")
    if len(values) > 64: raise ValueError("SIZE")
    if any(type(x) is not int or not -1_000_000 <= x <= 1_000_000 for x in values):
        raise ValueError("VALUE")
    return [algorithm(values, processors) for algorithm in
            (merge_sort, quick_sort, bitonic_sort, sample_sort)]

def format_results(results: list[Result]) -> str:
    lines: list[str] = []
    for r in results:
        lines.append("algorithm=" + r.name)
        for phase in r.phases:
            lines.append("  " + phase.label + " after=" + array_text(phase.after)
                         + f" waves={phase.waves}")
            for j, job in enumerate(phase.jobs):
                lines.append(f"    job={j} worker={job.worker} wave={job.wave} "
                             f"comparisons={job.comparisons} " + job.note)
        lines.append("  result=" + array_text(r.output)
                     + f" comparisons={r.comparisons} dispatch_waves={r.waves}")
    return "\n".join(lines)

if __name__ == "__main__":
    values = [7, 2, 5, 2, 9, 1, 8, 3]
    processors = 2
    print(f"input={array_text(values)} processors={processors}")
    print(format_results(sort_all(values, processors)))

#include <algorithm>
#include <iostream>
#include <sstream>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>
using Array = std::vector<int>;
struct Job { std::string note; int comparisons, worker, wave; };
struct Phase { std::string label; Array after; std::vector<Job> jobs; int waves; };
struct Result {
    std::string name;
    Array output;
    std::vector<Phase> phases;
    int comparisons = 0, waves = 0;
    explicit Result(std::string label) : name(std::move(label)) { }
};
const int PAD = 1000001;
std::string array_text(const Array& a) {
    std::ostringstream out; out << '[';
    for (std::size_t i = 0; i < a.size(); ++i) {
        if (i) out << ',';
        out << a[i];
    }
    out << ']'; return out.str();
}
Array slice(const Array& a, int lo, int hi) {
    return Array(a.begin() + lo, a.begin() + hi);
}
std::pair<Array,int> merge_parts(const Array& left, const Array& right) {
    Array out; std::size_t i = 0, j = 0; int count = 0;
    while (i < left.size() && j < right.size()) {
        ++count;
        if (left[i] <= right[j]) out.push_back(left[i++]);
        else out.push_back(right[j++]);
    }
    out.insert(out.end(), left.begin() + i, left.end());
    out.insert(out.end(), right.begin() + j, right.end());
    return {out, count};
}
std::pair<Array,int> local_sort(Array a) {
    int n = static_cast<int>(a.size()), count = 0;
    for (int width = 1; width < n; width *= 2) {
        Array out;
        for (int lo = 0; lo < n; lo += 2 * width) {
            auto piece = merge_parts(slice(a, lo, std::min(lo + width,n)),
                                     slice(a, std::min(lo + width,n), std::min(lo + 2*width,n)));
            out.insert(out.end(),piece.first.begin(),piece.first.end()); count += piece.second;
        }
        a = std::move(out);
    }
    return {a,count};
}
void emit(Result& r, const std::string& label, const Array& after,
          const std::vector<std::string>& notes, const Array& counts, int p) {
    Phase phase{label,after,{},0};
    for (int j = 0; j < static_cast<int>(notes.size()); ++j) {
        phase.jobs.push_back(Job{notes[j],counts[j],j % p,j / p});
        r.comparisons += counts[j];
    }
    phase.waves = (static_cast<int>(notes.size()) + p - 1) / p;
    r.waves += phase.waves; r.phases.push_back(phase);
}
Result merge_sort(Array a, int p) {
    Result r("merge"); int n = static_cast<int>(a.size());
    for (int width = 1; width < n; width *= 2) {
        Array out, counts; std::vector<std::string> notes;
        for (int lo = 0; lo < n; lo += 2 * width) {
            int mid = std::min(lo + width,n), hi = std::min(lo + 2*width,n);
            auto piece = merge_parts(slice(a,lo,mid),slice(a,mid,hi));
            out.insert(out.end(),piece.first.begin(),piece.first.end()); counts.push_back(piece.second);
            notes.push_back("range=[" + std::to_string(lo) + "," + std::to_string(hi)
                            + ") mid=" + std::to_string(mid));
        }
        emit(r,"width=" + std::to_string(width),out,notes,counts,p); a = std::move(out);
    }
    r.output = a; return r;
}
Result quick_sort(Array a, int p) {
    Result r("quick"); std::vector<std::pair<int,int>> tasks;
    if (a.size() > 1) tasks.emplace_back(0,static_cast<int>(a.size()));
    int depth = 0;
    while (!tasks.empty()) {
        Array out = a, counts; std::vector<std::string> notes;
        std::vector<std::pair<int,int>> next;
        for (auto task : tasks) {
            int lo = task.first, hi = task.second, pivot = a[(lo + hi)/2], c = 0;
            Array less, equal, greater;
            for (int i = lo; i < hi; ++i) {
                int x = a[i]; ++c;
                if (x < pivot) less.push_back(x);
                else { ++c; if (x > pivot) greater.push_back(x); else equal.push_back(x); }
            }
            Array piece = less;
            piece.insert(piece.end(),equal.begin(),equal.end());
            piece.insert(piece.end(),greater.begin(),greater.end());
            std::copy(piece.begin(),piece.end(),out.begin() + lo);
            int left_stop = lo + static_cast<int>(less.size());
            int right_start = left_stop + static_cast<int>(equal.size());
            if (left_stop - lo > 1) next.emplace_back(lo,left_stop);
            if (hi - right_start > 1) next.emplace_back(right_start,hi);
            notes.push_back("range=[" + std::to_string(lo) + "," + std::to_string(hi)
                 + ") pivot=" + std::to_string(pivot) + " sizes="
                 + array_text(Array{static_cast<int>(less.size()),static_cast<int>(equal.size()),static_cast<int>(greater.size())}));
            counts.push_back(c);
        }
        emit(r,"depth=" + std::to_string(depth++),out,notes,counts,p);
        a = std::move(out); tasks = std::move(next);
    }
    r.output = a; return r;
}
Result bitonic_sort(Array a, int p) {
    int n = static_cast<int>(a.size()), m = 1;
    while (m < n) m *= 2;
    if (n) a.resize(m,PAD);
    Result r("bitonic");
    for (int size = 2; size <= m && n; size *= 2) {
        for (int stride = size / 2; stride; stride /= 2) {
            Array out = a, counts; std::vector<std::string> notes;
            for (int i = 0; i < m; ++i) {
                int j = i ^ stride;
                if (j > i) {
                    bool ascending = (i & size) == 0;
                    int x = a[i], y = a[j];
                    if (ascending ? x > y : x < y) std::swap(x,y);
                    out[i] = x; out[j] = y;
                    notes.push_back("pair=" + std::to_string(i) + "," + std::to_string(j)
                                    + (ascending ? " ASC" : " DESC")); counts.push_back(1);
                }
            }
            emit(r,"size=" + std::to_string(size) + " stride=" + std::to_string(stride),out,notes,counts,p);
            a = std::move(out);
        }
    }
    a.resize(n); r.output = a; return r;
}
Result sample_sort(Array a, int p) {
    Result r("sample"); int n = static_cast<int>(a.size());
    if (n < 2) { r.output = a; return r; }
    int b = std::min(p,n), s = std::min(n,2*b); Array positions, sample;
    for (int i = 0; i < s; ++i) { positions.push_back(i*n/s); sample.push_back(a[i*n/s]); }
    auto ordered = local_sort(sample); sample = ordered.first;
    Array splitters;
    for (int j = 1; j < b; ++j) splitters.push_back(sample[j*s/b]);
    emit(r,"select splitters=" + array_text(splitters),a,
         {"sample_positions=" + array_text(positions) + " sorted=" + array_text(sample)}, {ordered.second},p);
    std::vector<Array> buckets(b); Array counts; std::vector<std::string> notes;
    for (int chunk = 0; chunk < b; ++chunk) {
        int lo = chunk*n/b, hi = (chunk+1)*n/b, c = 0;
        for (int i = lo; i < hi; ++i) {
            int left = 0, right = static_cast<int>(splitters.size());
            while (left < right) {
                int mid = (left + right)/2; ++c;
                if (a[i] < splitters[mid]) right = mid; else left = mid + 1;
            }
            buckets[left].push_back(a[i]);
        }
        notes.push_back("chunk=[" + std::to_string(lo) + "," + std::to_string(hi) + ")"); counts.push_back(c);
    }
    Array sizes, out;
    for (const auto& bucket : buckets) { sizes.push_back(static_cast<int>(bucket.size())); out.insert(out.end(),bucket.begin(),bucket.end()); }
    emit(r,"distribute sizes=" + array_text(sizes),out,notes,counts,p);
    out.clear(); notes.clear(); counts.clear(); int start = 0;
    for (int j = 0; j < b; ++j) {
        auto part = local_sort(buckets[j]); int stop = start + static_cast<int>(buckets[j].size());
        out.insert(out.end(),part.first.begin(),part.first.end()); counts.push_back(part.second);
        notes.push_back("bucket=" + std::to_string(j) + " range=[" + std::to_string(start) + "," + std::to_string(stop) + ")"); start = stop;
    }
    emit(r,"sort-buckets",out,notes,counts,p); r.output = out; return r;
}
std::vector<Result> sort_all(const Array& values, int p) {
    if (p < 1 || p > 16) throw std::invalid_argument("PROCESSORS");
    if (values.size() > 64) throw std::invalid_argument("SIZE");
    for (int x : values) if (x < -1000000 || x > 1000000) throw std::invalid_argument("VALUE");
    return {merge_sort(values,p),quick_sort(values,p),bitonic_sort(values,p),sample_sort(values,p)};
}
std::string format_results(const std::vector<Result>& results) {
    std::ostringstream out;
    for (const auto& r : results) {
        out << "algorithm=" << r.name << '\n';
        for (const auto& phase : r.phases) {
            out << "  " << phase.label << " after=" << array_text(phase.after) << " waves=" << phase.waves << '\n';
            for (std::size_t j = 0; j < phase.jobs.size(); ++j) {
                const auto& job = phase.jobs[j];
                out << "    job=" << j << " worker=" << job.worker << " wave=" << job.wave
                    << " comparisons=" << job.comparisons << ' ' << job.note << '\n';
            }
        }
        out << "  result=" << array_text(r.output) << " comparisons=" << r.comparisons
            << " dispatch_waves=" << r.waves << '\n';
    }
    auto s = out.str(); if (!s.empty()) s.pop_back(); return s;
}
int main() {
    Array values{7,2,5,2,9,1,8,3}; int processors = 2;
    std::cout << "input=" << array_text(values) << " processors=" << processors << '\n';
    std::cout << format_results(sort_all(values,processors)) << '\n';
    return 0;
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    static final int PAD = 1000001;
    static final class Job {
        String note;
        int comparisons, worker, wave;
        Job(String note, int comparisons, int worker, int wave) {
            this.note = note; this.comparisons = comparisons;
            this.worker = worker; this.wave = wave;
        }
    }
    static final class Phase {
        String label;
        List<Integer> after;
        List<Job> jobs = new ArrayList<>();
        int waves;
        Phase(String label, List<Integer> after) {
            this.label = label; this.after = new ArrayList<>(after);
        }
    }
    static final class Result {
        String name;
        List<Integer> output = new ArrayList<>();
        List<Phase> phases = new ArrayList<>();
        int comparisons, waves;
        Result(String name) { this.name = name; }
    }
    static final class Piece {
        List<Integer> values;
        int comparisons;
        Piece(List<Integer> values, int comparisons) {
            this.values = values; this.comparisons = comparisons;
        }
    }
    static String arrayText(List<Integer> values) {
        StringBuilder out = new StringBuilder("[");
        for (int i = 0; i < values.size(); ++i) {
            if (i != 0) out.append(',');
            out.append(values.get(i));
        }
        return out.append(']').toString();
    }
    static List<Integer> slice(List<Integer> a, int lo, int hi) {
        return new ArrayList<>(a.subList(lo,hi));
    }
    static Piece mergeParts(List<Integer> left, List<Integer> right) {
        List<Integer> out = new ArrayList<>(); int i = 0, j = 0, count = 0;
        while (i < left.size() && j < right.size()) {
            ++count;
            if (left.get(i) <= right.get(j)) out.add(left.get(i++));
            else out.add(right.get(j++));
        }
        out.addAll(left.subList(i,left.size())); out.addAll(right.subList(j,right.size()));
        return new Piece(out,count);
    }
    static Piece localSort(List<Integer> values) {
        List<Integer> a = new ArrayList<>(values); int n = a.size(), count = 0;
        for (int width = 1; width < n; width *= 2) {
            List<Integer> out = new ArrayList<>();
            for (int lo = 0; lo < n; lo += 2 * width) {
                Piece piece = mergeParts(slice(a,lo,Math.min(lo+width,n)),
                                        slice(a,Math.min(lo+width,n),Math.min(lo+2*width,n)));
                out.addAll(piece.values); count += piece.comparisons;
            }
            a = out;
        }
        return new Piece(a,count);
    }
    static void emit(Result r, String label, List<Integer> after,
                     List<String> notes, List<Integer> counts, int p) {
        Phase phase = new Phase(label,after);
        for (int j = 0; j < notes.size(); ++j) {
            phase.jobs.add(new Job(notes.get(j),counts.get(j),j % p,j / p));
            r.comparisons += counts.get(j);
        }
        phase.waves = (notes.size() + p - 1) / p;
        r.waves += phase.waves; r.phases.add(phase);
    }
    static Result mergeSort(List<Integer> values, int p) {
        List<Integer> a = new ArrayList<>(values); Result r = new Result("merge");
        int n = a.size();
        for (int width = 1; width < n; width *= 2) {
            List<Integer> out = new ArrayList<>(), counts = new ArrayList<>();
            List<String> notes = new ArrayList<>();
            for (int lo = 0; lo < n; lo += 2 * width) {
                int mid = Math.min(lo+width,n), hi = Math.min(lo+2*width,n);
                Piece piece = mergeParts(slice(a,lo,mid),slice(a,mid,hi));
                out.addAll(piece.values); counts.add(piece.comparisons);
                notes.add("range=[" + lo + "," + hi + ") mid=" + mid);
            }
            emit(r,"width=" + width,out,notes,counts,p); a = out;
        }
        r.output = a; return r;
    }
    static Result quickSort(List<Integer> values, int p) {
        List<Integer> a = new ArrayList<>(values); Result r = new Result("quick");
        List<int[]> tasks = new ArrayList<>();
        if (a.size() > 1) tasks.add(new int[]{0,a.size()});
        int depth = 0;
        while (!tasks.isEmpty()) {
            List<Integer> out = new ArrayList<>(a), counts = new ArrayList<>();
            List<String> notes = new ArrayList<>(); List<int[]> next = new ArrayList<>();
            for (int[] task : tasks) {
                int lo = task[0], hi = task[1], pivot = a.get((lo+hi)/2), c = 0;
                List<Integer> less = new ArrayList<>(), equal = new ArrayList<>(), greater = new ArrayList<>();
                for (int i = lo; i < hi; ++i) {
                    int x = a.get(i); ++c;
                    if (x < pivot) less.add(x);
                    else { ++c; if (x > pivot) greater.add(x); else equal.add(x); }
                }
                List<Integer> piece = new ArrayList<>(less); piece.addAll(equal); piece.addAll(greater);
                for (int i = 0; i < piece.size(); ++i) out.set(lo+i,piece.get(i));
                int leftStop = lo+less.size(), rightStart = leftStop+equal.size();
                if (leftStop-lo > 1) next.add(new int[]{lo,leftStop});
                if (hi-rightStart > 1) next.add(new int[]{rightStart,hi});
                notes.add("range=[" + lo + "," + hi + ") pivot=" + pivot + " sizes="
                          + arrayText(Arrays.asList(less.size(),equal.size(),greater.size())));
                counts.add(c);
            }
            emit(r,"depth=" + depth++,out,notes,counts,p); a = out; tasks = next;
        }
        r.output = a; return r;
    }
    static Result bitonicSort(List<Integer> values, int p) {
        int n = values.size(), m = 1;
        while (m < n) m *= 2;
        List<Integer> a = new ArrayList<>(values);
        if (n != 0) while (a.size() < m) a.add(PAD);
        Result r = new Result("bitonic");
        for (int size = 2; size <= m && n != 0; size *= 2) {
            for (int stride = size/2; stride != 0; stride /= 2) {
                List<Integer> out = new ArrayList<>(a), counts = new ArrayList<>();
                List<String> notes = new ArrayList<>();
                for (int i = 0; i < m; ++i) {
                    int j = i ^ stride;
                    if (j > i) {
                        boolean ascending = (i & size) == 0;
                        int x = a.get(i), y = a.get(j);
                        if (ascending ? x > y : x < y) { int temp = x; x = y; y = temp; }
                        out.set(i,x); out.set(j,y);
                        notes.add("pair=" + i + "," + j + (ascending ? " ASC" : " DESC")); counts.add(1);
                    }
                }
                emit(r,"size=" + size + " stride=" + stride,out,notes,counts,p); a = out;
            }
        }
        r.output = slice(a,0,n); return r;
    }
    static Result sampleSort(List<Integer> values, int p) {
        List<Integer> a = new ArrayList<>(values); int n = a.size(); Result r = new Result("sample");
        if (n < 2) { r.output = a; return r; }
        int b = Math.min(p,n), s = Math.min(n,2*b);
        List<Integer> positions = new ArrayList<>(), sample = new ArrayList<>();
        for (int i = 0; i < s; ++i) { positions.add(i*n/s); sample.add(a.get(i*n/s)); }
        Piece ordered = localSort(sample); sample = ordered.values;
        List<Integer> splitters = new ArrayList<>();
        for (int j = 1; j < b; ++j) splitters.add(sample.get(j*s/b));
        emit(r,"select splitters=" + arrayText(splitters),a,
             Arrays.asList("sample_positions=" + arrayText(positions) + " sorted=" + arrayText(sample)),
             Arrays.asList(ordered.comparisons),p);
        List<List<Integer>> buckets = new ArrayList<>();
        for (int j = 0; j < b; ++j) buckets.add(new ArrayList<>());
        List<Integer> counts = new ArrayList<>(); List<String> notes = new ArrayList<>();
        for (int chunk = 0; chunk < b; ++chunk) {
            int lo = chunk*n/b, hi = (chunk+1)*n/b, c = 0;
            for (int i = lo; i < hi; ++i) {
                int x = a.get(i), left = 0, right = splitters.size();
                while (left < right) {
                    int mid = (left+right)/2; ++c;
                    if (x < splitters.get(mid)) right = mid; else left = mid+1;
                }
                buckets.get(left).add(x);
            }
            notes.add("chunk=[" + lo + "," + hi + ")"); counts.add(c);
        }
        List<Integer> sizes = new ArrayList<>(), out = new ArrayList<>();
        for (List<Integer> bucket : buckets) { sizes.add(bucket.size()); out.addAll(bucket); }
        emit(r,"distribute sizes=" + arrayText(sizes),out,notes,counts,p);
        out = new ArrayList<>(); notes = new ArrayList<>(); counts = new ArrayList<>(); int start = 0;
        for (int j = 0; j < b; ++j) {
            Piece part = localSort(buckets.get(j)); int stop = start+buckets.get(j).size();
            out.addAll(part.values); counts.add(part.comparisons);
            notes.add("bucket=" + j + " range=[" + start + "," + stop + ")"); start = stop;
        }
        emit(r,"sort-buckets",out,notes,counts,p); r.output = out; return r;
    }
    static List<Result> sortAll(List<Integer> values, int p) {
        if (p < 1 || p > 16) throw new IllegalArgumentException("PROCESSORS");
        if (values.size() > 64) throw new IllegalArgumentException("SIZE");
        for (Integer x : values)
            if (x == null || x < -1000000 || x > 1000000) throw new IllegalArgumentException("VALUE");
        return Arrays.asList(mergeSort(values,p),quickSort(values,p),bitonicSort(values,p),sampleSort(values,p));
    }
    static String formatResults(List<Result> results) {
        StringBuilder out = new StringBuilder();
        for (Result r : results) {
            out.append("algorithm=").append(r.name).append('\n');
            for (Phase phase : r.phases) {
                out.append("  ").append(phase.label).append(" after=").append(arrayText(phase.after))
                   .append(" waves=").append(phase.waves).append('\n');
                for (int j = 0; j < phase.jobs.size(); ++j) {
                    Job job = phase.jobs.get(j);
                    out.append("    job=").append(j).append(" worker=").append(job.worker)
                       .append(" wave=").append(job.wave).append(" comparisons=").append(job.comparisons)
                       .append(' ').append(job.note).append('\n');
                }
            }
            out.append("  result=").append(arrayText(r.output)).append(" comparisons=")
               .append(r.comparisons).append(" dispatch_waves=").append(r.waves).append('\n');
        }
        if (out.length() != 0) out.setLength(out.length()-1);
        return out.toString();
    }
    public static void main(String[] args) {
        List<Integer> values = Arrays.asList(7,2,5,2,9,1,8,3); int processors = 2;
        System.out.println("input=" + arrayText(values) + " processors=" + processors);
        System.out.println(formatResults(sortAll(values,processors)));
    }
}

Identical expected output (each item is one printed line; numeric padding is 1000001):

• input=[7,2,5,2,9,1,8,3] processors=2
• algorithm=merge
• width=1 after=[2,7,2,5,1,9,3,8] waves=2
• job=0 worker=0 wave=0 comparisons=1 range=[0,2) mid=1
• job=1 worker=1 wave=0 comparisons=1 range=[2,4) mid=3
• job=2 worker=0 wave=1 comparisons=1 range=[4,6) mid=5
• job=3 worker=1 wave=1 comparisons=1 range=[6,8) mid=7
• width=2 after=[2,2,5,7,1,3,8,9] waves=1
• job=0 worker=0 wave=0 comparisons=3 range=[0,4) mid=2
• job=1 worker=1 wave=0 comparisons=3 range=[4,8) mid=6
• width=4 after=[1,2,2,3,5,7,8,9] waves=1
• job=0 worker=0 wave=0 comparisons=6 range=[0,8) mid=4
• result=[1,2,2,3,5,7,8,9] comparisons=16 dispatch_waves=4
• algorithm=quick
• depth=0 after=[7,2,5,2,1,8,3,9] waves=1
• job=0 worker=0 wave=0 comparisons=9 range=[0,8) pivot=9 sizes=[7,1,0]
• depth=1 after=[1,2,2,7,5,8,3,9] waves=1
• job=0 worker=0 wave=0 comparisons=13 range=[0,7) pivot=2 sizes=[1,2,4]
• depth=2 after=[1,2,2,7,5,3,8,9] waves=1
• job=0 worker=0 wave=0 comparisons=5 range=[3,7) pivot=8 sizes=[3,1,0]
• depth=3 after=[1,2,2,3,5,7,8,9] waves=1
• job=0 worker=0 wave=0 comparisons=5 range=[3,6) pivot=5 sizes=[1,1,1]
• result=[1,2,2,3,5,7,8,9] comparisons=32 dispatch_waves=4
• algorithm=bitonic
• size=2 stride=1 after=[2,7,5,2,1,9,8,3] waves=2
• job=0 worker=0 wave=0 comparisons=1 pair=0,1 ASC
• job=1 worker=1 wave=0 comparisons=1 pair=2,3 DESC
• job=2 worker=0 wave=1 comparisons=1 pair=4,5 ASC
• job=3 worker=1 wave=1 comparisons=1 pair=6,7 DESC
• size=4 stride=2 after=[2,2,5,7,8,9,1,3] waves=2
• job=0 worker=0 wave=0 comparisons=1 pair=0,2 ASC
• job=1 worker=1 wave=0 comparisons=1 pair=1,3 ASC
• job=2 worker=0 wave=1 comparisons=1 pair=4,6 DESC
• job=3 worker=1 wave=1 comparisons=1 pair=5,7 DESC
• size=4 stride=1 after=[2,2,5,7,9,8,3,1] waves=2
• job=0 worker=0 wave=0 comparisons=1 pair=0,1 ASC
• job=1 worker=1 wave=0 comparisons=1 pair=2,3 ASC
• job=2 worker=0 wave=1 comparisons=1 pair=4,5 DESC
• job=3 worker=1 wave=1 comparisons=1 pair=6,7 DESC
• size=8 stride=4 after=[2,2,3,1,9,8,5,7] waves=2
• job=0 worker=0 wave=0 comparisons=1 pair=0,4 ASC
• job=1 worker=1 wave=0 comparisons=1 pair=1,5 ASC
• job=2 worker=0 wave=1 comparisons=1 pair=2,6 ASC
• job=3 worker=1 wave=1 comparisons=1 pair=3,7 ASC
• size=8 stride=2 after=[2,1,3,2,5,7,9,8] waves=2
• job=0 worker=0 wave=0 comparisons=1 pair=0,2 ASC
• job=1 worker=1 wave=0 comparisons=1 pair=1,3 ASC
• job=2 worker=0 wave=1 comparisons=1 pair=4,6 ASC
• job=3 worker=1 wave=1 comparisons=1 pair=5,7 ASC
• size=8 stride=1 after=[1,2,2,3,5,7,8,9] waves=2
• job=0 worker=0 wave=0 comparisons=1 pair=0,1 ASC
• job=1 worker=1 wave=0 comparisons=1 pair=2,3 ASC
• job=2 worker=0 wave=1 comparisons=1 pair=4,5 ASC
• job=3 worker=1 wave=1 comparisons=1 pair=6,7 ASC
• result=[1,2,2,3,5,7,8,9] comparisons=24 dispatch_waves=12
• algorithm=sample
• select splitters=[8] after=[7,2,5,2,9,1,8,3] waves=1
• job=0 worker=0 wave=0 comparisons=4 sample_positions=[0,2,4,6] sorted=[5,7,8,9]
• distribute sizes=[6,2] after=[7,2,5,2,1,3,9,8] waves=1
• job=0 worker=0 wave=0 comparisons=4 chunk=[0,4)
• job=1 worker=1 wave=0 comparisons=4 chunk=[4,8)
• sort-buckets after=[1,2,2,3,5,7,8,9] waves=1
• job=0 worker=0 wave=0 comparisons=10 bucket=0 range=[0,6)
• job=1 worker=1 wave=0 comparisons=1 bucket=1 range=[6,8)
• result=[1,2,2,3,5,7,8,9] comparisons=23 dispatch_waves=3

Complexity, Correctness, and Invariants

Use constant-time integer comparisons and word-sized keys. The conceptual asymptotic bounds describe the same algorithms without the teaching API's size cap. Distinguish algorithmic work, parallel span with specified primitives, the sequential simulator, and saved trace space. No universal parallel-sorting runtime follows from the names alone.

Merge sort. With sequential merging, $W(n)=2W(n/2)+\Theta(n)=\Theta(n\log n)$ for best, average, and worst cases of this non-adaptive version. The critical path includes the final linear-size merge: $D(n)=D(n/2)+\Theta(n)=\Theta(n)$. Parallelizing only the two recursive sorts leaves this bottleneck intact. More advanced work-efficient merge primitives with linear work and logarithmic span can give a merge-sort span $O(\log^2n)$; a simple binary-search recursive merge can have a larger span, so state the primitive before quoting a bound. A separate output buffer needs $O(n)$ space; saving n entries at each merge width raises retained trace space to $O(n\log n)$ here.

Quicksort. Three-way partitioning performs linear work on its active range. Balanced distinct-key partitions give $\Theta(n\log n)$ total partition work and, with the shown sequential partition primitive, $\Theta(n)$ span. Random pivots give expected $O(n\log n)$ work, but our deterministic middle-position pivot is not randomized and has no input-independent expected guarantee. Repeated extreme pivots can give $\Theta(n^2)$ work and span. All-equal data finishes in one linear partition, so best-case work is $\Theta(n)$ for this three-way variant. An average-case claim needs a stated input distribution; uniform random permutations of distinct keys support the familiar expected bounds. With work-efficient parallel partitions of $O(\log n)$ span and sufficiently balanced/random recursion, expected span can instead be $O(\log^2n)$; that is a different primitive from the code.

The trace simulator copies and stores a full n-entry array at every quicksort depth, even when only a small range remains active. If there are h partition depths, this adds $O(nh)$ work and retained state: $O(n\log n)$ for balanced recursion and $O(n^2)$ in the worst case. Working buffers alone are $O(n)$ without retaining history. The breadth-first task list avoids host recursion-stack overflow, but it does not prevent bad pivots.

Bitonic network. For positive n, let $m=2^k$ be the smallest power of two at least n, with $k=\lceil\log_2n\rceil$ and $n\le m\lt2n$. Size $2^r$ uses r comparator stages. Therefore

$$L=\sum_{r=1}^{k}r=\frac{k(k+1)}2,\qquad C=\frac{m}{2}L=\frac{mk(k+1)}4.$$

For $m\ge2$, work is $\Theta(m\log^2m)$ and comparator span is $L=\Theta(\log^2m)$. The fixed schedule does exactly the same comparisons for sorted, reversed, equal, random, best, average, and worst inputs. Padding gives the same asymptotic bounds in n for $n\ge2$. With P workers and full-stage barriers, the unit-comparator wave count is exactly

$$R_P=L\left\lceil\frac{m/2}{P}\right\rceil.$$

Thus $R_P=\Theta(m\log^2m/P+\log^2m)$ under this unit-cost comparator model. For $m=8$, $L=6$, $C=24$, and $R_2=12$. This excludes allocation, full snapshots, worker startup, synchronization cost, and memory transfer. Empty/singleton inputs have zero comparator stages and comparisons. Buffers need $O(m)$ working space; full stage history and explicit job descriptions take $O(m\log^2m)$ records here. A streaming or in-place network can discard those histories.

Sample sort. Let sample size S, bucket count B, and bucket sizes $b_0,\ldots,b_{B-1}$ sum to n. The implemented local merge helper has $O(t\log(t+1))$ work on t keys. Work for sample sorting, binary classification, and local bucket sorting is bounded by

$$O\!\left(S\log(S+1)+n\log(B+1)+\sum_{j=0}^{B-1}b_j\log(b_j+1)+n+B\right).$$

Since $S\le n$, $B\le n$, and all buckets together contain n keys, this is $O(n\log(n+1))$ even when all keys fall into one bucket; correctness and the work bound do not imply balanced execution. Under ideal independent bucket workers, the slowest local sort depends on $b_{\max}=\max_jb_j$. Balanced buckets make this term $O((n/B)\log(n/B+1))$; one bucket containing n keys gives $O(n\log n)$ instead. Add sample selection/sorting, classification, prefix-offset/scatter, and communication costs before claiming an end-to-end parallel time. Our deterministic positional sampling provides no probabilistic balance guarantee. Random oversampling needs explicit distribution/probability assumptions and duplicate handling; it is not justified by this trace. Sample-sort working space and its three retained global arrays are $O(n+B+S)=O(n)$ for this version. Best/average/worst comparison counts depend on sample choices, distributions, and merge interleavings; the displayed bound is a worst-case upper bound, not an asserted tight bound for every input.

Correctness: three reusable arguments and one network lemma. Merge jobs preserve their two runs' multisets and produce sorted unions. Inducting on run width gives a sorted permutation of the whole input. Quick partition jobs preserve every occurrence, establish $\text{less}\lt\text{pivot}=\text{equal}\lt\text{greater}$ between groups, and recurse only on strictly smaller disjoint ranges; induction yields sorted ranges and their sorted concatenation. Sample classification assigns each occurrence to exactly one bucket; all keys in an earlier bucket are at most all keys in a later bucket. Sorting each bucket and concatenating therefore yields a sorted permutation, including with repeated splitters and empty buckets.

For bitonic sorting, every comparator preserves multiplicity. The bitonic-split lemma says that comparing opposite halves of a bitonic sequence places smaller values in one half and larger values in the other, leaves each half bitonic, and separates the halves so every key in the lower half is at most every key in the upper half. Recursing on half-size subproblems sorts the whole bitonic sequence in the requested direction. One way to understand the lemma is to threshold keys into zeros and ones: in a bitonic binary cycle, the ones form one circular interval, so opposite-pair min/max separation cannot leave a larger lower-half key above a smaller upper-half key. Induction on size starts from singleton runs, combines alternating ascending/descending runs into a bitonic block, and applies the lemma to sort each larger block. Final size m is ascending; padding keys then occupy the end and trimming them preserves exactly the real input.

All four proofs also require disjoint destination ownership and barriers. A correct sequential state transition does not automatically remain correct after introducing concurrent writes. Best/average/worst host runtime additionally includes history copies and formatting; the program's dispatch counters are never a substitute for measuring that runtime.

Variants, Pitfalls, and Optimizations

Sorting chunks is only a starting point. Arbitrary sorted chunks can overlap in key range, as [1,7] and [2,8] do. Merge them instead of simply concatenating. Sample-sort buckets are different: their splitter-defined ranges already establish cross-bucket order, so concatenation is valid after local sorting. Test the last key of each nonempty run/bucket against the first key of the next one.

Partition balance and progress are separate checks. Our quicksort always progresses because the pivot occurs in the segment and the equal band is excluded from further tasks. Nevertheless, a deterministic middle-position pivot can be an extreme key repeatedly on a carefully arranged input. Random pivots, stronger selection, task cutoffs, and an introspective fallback can improve robustness. Three-way partitions prevent all-equal keys from recurring pointlessly. Avoid spawning tasks for empty/singleton ranges or using shared append structures without exclusive ownership.

Sample sort can be correct and badly skewed. Duplicate splitters plus upper-bound assignment put all keys equal to the final splitter in the same bucket. Eight copies of 2 with splitter 2 produce sizes $[0,8]$. More random oversampling improves estimates for many distributions, but cannot by itself separate identical keys under this exact tie rule. Equality buckets, balanced assignment of equal keys, or sorting by $(\text{key},\text{original index})$ can distribute ties; state how each choice affects stability and ordering. Regular input positions can miss structure, so do not attach a high-probability balance claim to the deterministic teaching sample. Production PSRS variants often sort local blocks and choose regular samples from those sorted blocks; that is not the same as sampling raw input positions here.

Bitonic directions and barriers are essential. Sorting every early pair ascending breaks the construction. On [3,1,2,0], making both size-2 pairs ascending and then running the final ascending size-4 merge leaves [0,2,1,3] unsorted. The XOR pattern must execute each pair once, and each stride must read a finished state. Intermediate directions intentionally move some large keys left, including padding; trim only after the final ascending size. If input keys can equal or exceed the padding sentinel, the current padding proof fails. Use tagged sentinels or a supported arbitrary-length network instead of silently skipping out-of-range partners in this power-of-two construction.

Stability needs record-level evidence. Left-first stable merging, stable three-way filtering, and stable bucket assembly can preserve equal-key record order when payloads are carried along. A bitonic network can reverse equal-key records indirectly even when equal pairs never swap. To require stable results from all families, compare decorated records lexicographically by key and original index, then remove the decoration. This changes pivot equality and splitter behavior, so analyze those versions separately. The integer-only programs verify multiplicity but do not demonstrate preservation of equal-key record identities.

Choose the unit of parallelism carefully. Parallel recursive calls with a serial root merge or root partition can leave linear span. Replacing a large job with scan/scatter or co-ranked output pieces increases available concurrency, but also adds setup. Tiny partitions and runs should usually use a tuned local sorter rather than more tasks. Reuse buffers, batch small work, reduce false sharing, and keep each worker's destination ranges disjoint. In distributed sample sort, count exchange, routing, all-to-all traffic, and peak receive memory can dominate comparison work. A low comparison count does not establish lower communication cost.

Comparator and benchmark pitfalls. Integer order here avoids NaNs and inconsistent user comparators. If sorting floats, define how NaNs and signed zeros are ordered. For records, compare keys without subtracting them into an overflowing integer. Benchmark equal input copies against a strong sequential baseline, include or explicitly separate allocation/transfer costs, and report distributions, sizes, P, stability requirements, and timing variability. No elapsed-time claims can be inferred from this simulator.

When another family fits better. A fixed bitonic pattern is attractive for small fixed-size vector/GPU tiles, while its extra logarithmic work factor can be expensive on large general inputs. Merging fits existing sorted runs and external sorting; quicksort variants fit partition-oriented shared-memory workloads; sample sort fits redistribution into global key ranges when sampling and communication are engineered well. Integer radix sorting can avoid comparison-sort lower bounds by exploiting digit structure, and selection/top-k methods may avoid a complete sort when only a few ranks are needed. Choose from measured workload constraints rather than one universal winner.

Practice Problems and Real-World Use

Begin with a trusted sequential reference and verify both nondecreasing order and identical occurrence counts. Then inspect the intermediate invariant appropriate to the family: merge runs are sorted unions of their original windows; quick partition bands obey their pivot inequalities; completed bitonic size blocks alternate direction; sample buckets obey their key ranges and preserve all occurrences.

Test empty/singleton inputs, ordered/reversed arrays, all equal keys, negatives, duplicates, extreme accepted values, and lengths just below/at/above powers of two. For bitonic networks, exhaustive binary tests on small fixed sizes provide especially strong structural coverage: the zero-one principle says a comparator network that correctly sorts every binary input sorts arbitrary ordered keys. Our test suite includes every one of the 256 binary arrays of length eight, in addition to direct integer tests. Larger networks still require their inductive proof and implementation checks; one small exhaustive size does not verify every size automatically.

Vary P while retaining input. Merge/quick/bitonic output and their phase states should remain unchanged; only worker/wave assignments change. Sample sort also changes B, its sample, splitters, and intermediate buckets with P, but its final sorted output must remain identical. Inject invalid worker counts and unsupported keys and confirm validation occurs before any sorting. For payloads, extend tests to unique record IDs and verify each occurrence appears once; require original equal-key ID order only when stability is part of the contract.

A useful implementation progression is: sequential trace; real tasks with barriers and private destinations; parallel merge or partition primitives; then hardware-specific or distributed optimization. Keep the reference and intermediate checks throughout. For sample-sort scatter, derive per-chunk bucket counts and exclusive prefix offsets so two workers never claim the same destination. For each benchmark, separate total work, communication, task imbalance, and measured wall-clock time.

Further reading: NIST's bitonic-sort entry describes fixed comparator scheduling. CMU's parallel sorting discussion develops parallel merge/quick approaches and granularity control. Practical Massively Parallel Sorting examines engineered sample/multiway-merge methods and communication at scale. These primary sources provide context; the exact counters and deterministic sample rule above belong to this lesson's implementations.