Bitonic Sorter in Verilog: Sorting Network with Code

module bitonic_sort #(parameter N=8, parameter W=8) (
  input  [N*W-1:0] in_flat,
  output [N*W-1:0] out_flat
);
  integer k, j, i, l, idx;
  reg [W-1:0] a [0:N-1];
  reg [W-1:0] t;
  always @(*) begin
    for (idx=0; idx<N; idx=idx+1)
      a[idx] = in_flat[idx*W +: W];
    for (k=2; k<=N; k=k*2)
      for (j=k/2; j>0; j=j/2)
        for (i=0; i<N; i=i+1) begin
          l = i ^ j;
          if (l > i) begin
            if ((i & k) == 0) begin
              if (a[i] > a[l]) begin t = a[i]; a[i] = a[l]; a[l] = t; end
            end else begin
              if (a[i] < a[l]) begin t = a[i]; a[i] = a[l]; a[l] = t; end
            end
          end
        end
  end
  genvar g;
  generate
    for (g=0; g<N; g=g+1) begin: pack
      assign out_flat[g*W +: W] = a[g];
    end
  endgenerate
endmodule

module tb;
  localparam N = 8, W = 8;
  reg  [N*W-1:0] in_flat;
  wire [N*W-1:0] out_flat;
  reg  [W-1:0] ref_arr [0:N-1];
  reg  [W-1:0] tmp;
  integer p, q, c;
  reg fail, any_fail;

  bitonic_sort #(.N(N), .W(W)) dut (.in_flat(in_flat), .out_flat(out_flat));

  task run_vec;
    input [N*W-1:0] vec;
    begin
      in_flat = vec;
      for (c = 0; c < N; c = c + 1) ref_arr[c] = vec[c*W +: W];
      for (p = 0; p < N; p = p + 1)
        for (q = 0; q < N-1; q = q + 1)
          if (ref_arr[q] > ref_arr[q+1]) begin
            tmp = ref_arr[q]; ref_arr[q] = ref_arr[q+1]; ref_arr[q+1] = tmp;
          end
      #1;
      fail = 0;
      for (c = 0; c < N; c = c + 1)
        if (out_flat[c*W +: W] !== ref_arr[c]) fail = 1;
      if (fail) begin
        any_fail = 1;
        $display("FAIL: in=%h out=%h", in_flat, out_flat);
      end else
        $display("PASS: sorted out=%h", out_flat);
    end
  endtask

  initial begin
    any_fail = 0;
    run_vec({8'd50,8'd10,8'd90,8'd30,8'd70,8'd20,8'd80,8'd40});
    run_vec({8'd8,8'd7,8'd6,8'd5,8'd4,8'd3,8'd2,8'd1});
    run_vec({8'd1,8'd2,8'd3,8'd4,8'd5,8'd6,8'd7,8'd8});
    run_vec({8'd255,8'd0,8'd128,8'd128,8'd1,8'd254,8'd77,8'd77});
    run_vec({8'd5,8'd5,8'd5,8'd5,8'd5,8'd5,8'd5,8'd5});
    run_vec({8'd200,8'd3,8'd201,8'd3,8'd0,8'd199,8'd3,8'd255});
    if (!any_fail) $display("ALL TESTS PASSED");
    $finish;
  end
endmodule

PASS: sorted out=5a504632281e140a
PASS: sorted out=0807060504030201
PASS: sorted out=0807060504030201
PASS: sorted out=fffe80804d4d0100
PASS: sorted out=0505050505050505
PASS: sorted out=ffc9c8c703030300
ALL TESTS PASSED
The log shows one PASS line per stimulus vector and a final ALL TESTS PASSED. Each PASS means the network output exactly matched a bubble-sorted reference of the same input built in the testbench, so the output is both fully sorted and a permutation of the inputs. Duplicate-heavy and min/max vectors are covered, so a wiring or comparator-direction bug would surface as a FAIL.

This parameterized variant (shown at N=4) adds a runtime dir input: the direction of every compare-exchange is flipped together, so the same network sorts ascending when dir=1 and descending when dir=0. The testbench checks both directions across several vectors against a reference sort that is reversed for the descending case.
bitonic_sort_dir.vSimulation log
module bitonic_sort_dir #(parameter N=4, parameter W=8) (
  input            dir,        // 1 = ascending, 0 = descending
  input  [N*W-1:0] in_flat,
  output [N*W-1:0] out_flat
);
  integer k, j, i, l, idx;
  reg up;
  reg [W-1:0] a [0:N-1];
  reg [W-1:0] t;
  always @(*) begin
    for (idx=0; idx<N; idx=idx+1)
      a[idx] = in_flat[idx*W +: W];
    for (k=2; k<=N; k=k*2)
      for (j=k/2; j>0; j=j/2)
        for (i=0; i<N; i=i+1) begin
          l = i ^ j;
          if (l > i) begin
            up = dir ? ((i & k) == 0) : ((i & k) != 0);
            if (up) begin
              if (a[i] > a[l]) begin t = a[i]; a[i] = a[l]; a[l] = t; end
            end else begin
              if (a[i] < a[l]) begin t = a[i]; a[i] = a[l]; a[l] = t; end
            end
          end
        end
  end
  genvar g;
  generate
    for (g=0; g<N; g=g+1) begin: pack
      assign out_flat[g*W +: W] = a[g];
    end
  endgenerate
endmodule

module tb;
  localparam N = 4, W = 8;
  reg  [N*W-1:0] in_flat;
  reg            dir;
  wire [N*W-1:0] out_flat;
  reg  [W-1:0] ref_arr [0:N-1];
  reg  [W-1:0] tmp;
  integer p, q, c;
  reg fail, any_fail;

  bitonic_sort_dir #(.N(N), .W(W)) dut (.dir(dir), .in_flat(in_flat), .out_flat(out_flat));

  task run_vec;
    input [N*W-1:0] vec;
    input          d;
    begin
      in_flat = vec; dir = d;
      for (c = 0; c < N; c = c + 1) ref_arr[c] = vec[c*W +: W];
      // bubble sort ascending
      for (p = 0; p < N; p = p + 1)
        for (q = 0; q < N-1; q = q + 1)
          if (ref_arr[q] > ref_arr[q+1]) begin
            tmp = ref_arr[q]; ref_arr[q] = ref_arr[q+1]; ref_arr[q+1] = tmp;
          end
      // if descending requested, reverse the reference
      if (!d) begin
        for (p = 0; p < N/2; p = p + 1) begin
          tmp = ref_arr[p]; ref_arr[p] = ref_arr[N-1-p]; ref_arr[N-1-p] = tmp;
        end
      end
      #1;
      fail = 0;
      for (c = 0; c < N; c = c + 1)
        if (out_flat[c*W +: W] !== ref_arr[c]) fail = 1;
      if (fail) begin
        any_fail = 1;
        $display("FAIL: dir=%b in=%h out=%h", dir, in_flat, out_flat);
      end else
        $display("PASS: dir=%b out=%h", dir, out_flat);
    end
  endtask

  initial begin
    any_fail = 0;
    run_vec({8'd30,8'd10,8'd40,8'd20}, 1'b1);
    run_vec({8'd30,8'd10,8'd40,8'd20}, 1'b0);
    run_vec({8'd1,8'd2,8'd3,8'd4},     1'b1);
    run_vec({8'd1,8'd2,8'd3,8'd4},     1'b0);
    run_vec({8'd255,8'd0,8'd77,8'd77}, 1'b1);
    run_vec({8'd255,8'd0,8'd77,8'd77}, 1'b0);
    run_vec({8'd9,8'd9,8'd9,8'd9},     1'b1);
    if (!any_fail) $display("ALL TESTS PASSED");
    $finish;
  end
endmodule
PASS: dir=1 out=281e140a
PASS: dir=0 out=0a141e28
PASS: dir=1 out=04030201
PASS: dir=0 out=01020304
PASS: dir=1 out=ff4d4d00
PASS: dir=0 out=004d4dff
PASS: dir=1 out=09090909
ALL TESTS PASSED
The log alternates dir=1 (ascending) and dir=0 (descending) PASS lines. Each PASS confirms the output matched the reference order for that direction, proving the direction-select logic inverts the whole network consistently rather than only part of it. The closing ALL TESTS PASSED covers both polarities plus a duplicate vector.

The compare-exchange primitive
Every sorting network is built from one block: the compare-exchange (CE) element. It takes two inputs and emits them in a fixed order — for an ascending CE, the smaller value leaves on the low output and the larger on the high output. In the code this is simply:
if (a[i] > a[l]) begin t = a[i]; a[i] = a[l]; a[l] = t; end
A descending CE is the mirror image (swap when a[i] < a[l]). A sorting network is nothing more than a specific wiring of these blocks; the art is choosing which pairs to compare, in what order, so that any input ends up fully sorted.
Bitonic sequences and the merge network
A sequence is bitonic if it rises then falls (or is a rotation of such a sequence) — for example 1 4 6 5 3 2. The key property is that a bitonic sequence can be sorted by a bitonic merge: compare-exchange element i with element i+N/2, which splits it into two half-length bitonic sequences where every element of the low half is ≤ every element of the high half. Recursing on each half fully sorts it.
Bitonic sort builds a sorted sequence bottom-up. It first forms length-2 bitonic sequences, merges them into sorted length-2 runs (alternating ascending/descending to keep things bitonic at the next level), then merges those into bitonic length-4 sequences, and so on. In the Verilog this is exactly the three nested loops: k is the size of the bitonic sequence being merged, j is the current compare distance (i ^ j gives the partner), and the (i & k) bit chooses ascending or descending for that sub-block.
Stage and comparator count
For N = 2p elements, bitonic sort uses p = log2N merge phases, and phase number m contains m comparison stages. The total number of stages is therefore 1 + 2 + … + p = p(p+1)/2 = O(log2N). Each stage performs N/2 compare-exchanges, so the comparator count is (N/4)·log2N·(log2N+1) = O(N log2N).
N = 8: 3 phases, 6 stages, 24 comparators.
N = 16: 4 phases, 10 stages, 80 comparators.
N = 4: 2 phases, 3 stages, 6 comparators.
Latency (in CE stages) is the stage count; throughput is one vector per clock if you register between stages. This is more comparators than an asymptotically optimal AKS network, but bitonic sort wins in practice because its wiring is regular, local, and trivial to lay out and pipeline.
Why data-independent networks suit hardware
In a comparison sort like quicksort, the sequence of comparisons depends on the data, so control flow branches and latency varies. A sorting network makes the same comparisons in the same order for every input — only the data flowing through the CE blocks changes. That is ideal for hardware:
Fixed latency: every input takes exactly the same number of stages, so timing closure and scheduling are deterministic.
Full parallelism: all N/2 comparisons in a stage are independent and run concurrently.
Easy pipelining: insert registers between stages to get one-result-per-clock throughput.
No control logic: no comparators-counter, no loop state in silicon — the loops in the Verilog are unrolled at elaboration into pure wiring.
This is why sorting networks appear in routers, median filters, top-k accelerators, and sort-merge database engines.
Ascending vs descending, and common mistakes
The direction of the overall sort is set by the direction of the final merge phase, which propagates back through the (i & k) test. Example 2 flips this with a single dir multiplexer per comparator; note that you must invert every comparator together — inverting only some produces a bitonic (not sorted) result.
Common mistakes
Non-power-of-two N: the plain bitonic network only works when N is a power of two. For other sizes, pad up to the next power of two with sentinel values (0 or max) or use a merge-sort-style padding network.
Wrong partner index: the partner is i ^ j, not i + j. Using addition breaks the butterfly wiring for the larger j values.
Comparing a pair twice: guard with if (l > i) so each unordered pair is processed exactly once; without it you compare-exchange both (i,l) and (l,i) and may undo the swap.
Mixing up the direction bit: (i & k)==0 selects ascending for that block in an ascending overall sort; getting this inverted yields a reverse-sorted or bitonic output.
Synthesis notes and FAQ
Both modules are synthesizable: the for loops have compile-time bounds and unroll into a flat comparator network, and the reg arrays assigned inside always @(*) become combinational nets, not flip-flops. To pipeline, split the single combinational block into per-stage always @(posedge clk) blocks with pipeline registers between them — one register bank per CE stage.
Is a bitonic sorter stable?
No. Like most sorting networks it is not stable; equal keys may be reordered. If you need stability, append the original index as low-order tie-break bits to each key before sorting.
How do I sort signed numbers?
Either use signed comparisons in the CE ($signed(a[i]) > $signed(a[l])) or invert the MSB of each key so a standard unsigned compare orders them correctly.
What is the area/latency trade-off vs an odd-even network?
Bitonic and Batcher odd-even merge networks both use O(N log2N) comparators and O(log2N) depth; bitonic has slightly more comparators but a more uniform, easier-to-route structure, which is why it is the common choice for FPGA and ASIC sort accelerators.
Have questions about this topic?
Share your question in comments or talk to our mentor team for batch guidance.
▶ Try it in the ChipXpert Lab
Open this design in the free in-browser simulator — edit, compile and see the waveform/log instantly.
Run it in the Lab
Learn Verilog with mentors, labs and placement support
This free series is maintained by the ChipXpert training team in Hyderabad & Bengaluru. Go deeper with instructor-led courses on real EDA tools.
Explore VLSI Courses