<ahref="#ParallelMergeAlgorithmCorank">Step 2: Co-rank to Identify Input Subranges</a>
</li>
<liclass="level2">
<ahref="#ParallelMergeAlgorithmBinarySearch">Step 3: How co_rank works? Binary Search!</a>
</li>
<liclass="level2">
<ahref="#ParallelMergeAlgorithmNoPartitioner">Why parallel merge uses no partitioner</a>
</li>
</ul>
</li>
</ul>
</div>
<divclass="textblock"><p>Taskflow provides a function for constructing a task to merge two sorted ranges into a single sorted output range in parallel.</p>
</div><!-- fragment --><h1><aclass="anchor" id="ParallelMergeMotivation"></a>
Motivation</h1>
<p>The standard library <code>std::merge</code> walks both input sequences simultaneously from left to right in a single thread, producing a sorted output in O(n+m) time. While optimal for a single core, this sequential walk cannot exploit multiple CPU cores — at any point only one comparison is in flight. For large inputs (e.g. merging two sorted arrays of tens of millions of elements), this leaves the majority of available hardware idle.</p>
<p>Taskflow's parallel merge divides the output into <code>W</code> independent chunks (one per worker thread) and uses the <em>co-rank</em> technique to identify each worker's exact input sub-ranges, allowing all workers to merge their chunks simultaneously with no synchronization.</p>
<divclass="dotgraph">
<iframescrolling="no" frameborder="0" src="dot_merge_overview.svg" width="736" height="452"><p><b>This browser is not able to show SVG: try Firefox, Chrome, Safari, or Opera instead.</b></p></iframe></div>
<p>The task created by <aclass="el" href="classtf_1_1FlowBuilder.html#adba094978bb2c038163e0b1b18141efa" title="merges two sorted ranges into a single sorted output using the std::less comparator">tf::Taskflow::merge(B1 first1, E1 last1, B2 first2, E2 last2, O d_first)</a> merges the two sorted ranges <code>[first1, last1)</code> and <code>[first2, last2)</code> into the output range beginning at <code>d_first</code>, using <code>std::less</code> as the comparator. It represents the parallel execution of <code>std::merge:</code></p>
<divclass="line"><spanclass="comment">// output is now the sorted merge of seq1 and seq2</span></div>
<divclass="ttc" id="aclasstf_1_1Executor_html"><divclass="ttname"><ahref="classtf_1_1Executor.html">tf::Executor</a></div><divclass="ttdoc">class to create an executor</div><divclass="ttdef"><b>Definition</b> executor.hpp:62</div></div>
<divclass="ttc" id="aclasstf_1_1FlowBuilder_html_adba094978bb2c038163e0b1b18141efa"><divclass="ttname"><ahref="classtf_1_1FlowBuilder.html#adba094978bb2c038163e0b1b18141efa">tf::FlowBuilder::merge</a></div><divclass="ttdeci">Task merge(B1 first1, E1 last1, B2 first2, E2 last2, O d_first)</div><divclass="ttdoc">merges two sorted ranges into a single sorted output using the std::less comparator</div></div>
<divclass="ttc" id="aclasstf_1_1Taskflow_html"><divclass="ttname"><ahref="classtf_1_1Taskflow.html">tf::Taskflow</a></div><divclass="ttdoc">class to create a taskflow object</div><divclass="ttdef"><b>Definition</b> taskflow.hpp:64</div></div>
</div><!-- fragment --><p>To merge with a custom comparator, pass it as the last argument. Both input ranges must be sorted with respect to that comparator:</p>
</div><!-- fragment --><dlclass="section note"><dt>Note</dt><dd>Both input ranges must be sorted with respect to the comparator before the merge task runs. Passing unsorted input is undefined behavior. The output range must not overlap either input range. Both input iterators must be random-access iterators.</dd></dl>
<p>You can pass iterators by reference using <ahref="https://en.cppreference.com/w/cpp/utility/functional/ref">std::ref</a> to marshal parameter updates between dependent tasks. This is useful when the ranges are not known at task-graph construction time but are initialized by an upstream task.</p>
<divclass="ttc" id="aclasstf_1_1FlowBuilder_html_a4d52a7fe2814b264846a2085e931652c"><divclass="ttname"><ahref="classtf_1_1FlowBuilder.html#a4d52a7fe2814b264846a2085e931652c">tf::FlowBuilder::emplace</a></div><divclass="ttdeci">Task emplace(C &&callable)</div><divclass="ttdoc">creates a static task</div><divclass="ttdef"><b>Definition</b> flow_builder.hpp:1781</div></div>
<divclass="ttc" id="aclasstf_1_1Task_html"><divclass="ttname"><ahref="classtf_1_1Task.html">tf::Task</a></div><divclass="ttdoc">class to create a task handle over a taskflow node</div><divclass="ttdef"><b>Definition</b> task.hpp:569</div></div>
<divclass="ttc" id="aclasstf_1_1Task_html_a8c78c453295a553c1c016e4062da8588"><divclass="ttname"><ahref="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">tf::Task::precede</a></div><divclass="ttdeci">Task & precede(Ts &&... tasks)</div><divclass="ttdoc">adds precedence links from this to other tasks</div><divclass="ttdef"><b>Definition</b> task.hpp:1305</div></div>
</div><!-- fragment --><p>When <code>init</code> finishes, the merge task reads the updated iterators and merges the two runtime-defined sequences.</p>
<p>The merged output has <code>N</code> = n + m elements (where<code>n = |seq1|</code> and <code>m = |seq2|</code>). <br/>
The algorithm divides the output into <code>W</code> equal contiguous chunks of size <code>K = N/W</code>, one per worker thread. Worker <code>w</code> is responsible for writing output positions <code>[w*K, (w+1)*K)</code>. The key challenge here is that for each output chunk, which elements of <code>seq1</code> and <code>seq2</code> belong to it? This is what the co-rank function solves.</p>
<p>For a given output position <code>rank</code>, <code>co_rank(rank)</code> finds <code>i</code> and <code>j</code> such that:</p>
<ul>
<li>The first <code>rank</code> elements of the merged output consist of exactly <code>i</code> elements from <code>seq1</code>[0..i) and <code>j</code> elements from <code>seq2</code>[0..j).</li>
<li>These <code>i</code> + <code>j</code> elements are <em>interleaved</em> in sorted order in the output. Note that <code>co_rank</code> does not decide how they go in blocks but only identifies <em>how</em> many elements come from each sequence. The actual placement of these elements are accomplished via std::merge.</li>
</ul>
<p>Once a worker knows <code>(i_start, j_start)</code> at its chunk's beginning and <code>(i_end, j_end)</code> at its chunk's end, it can independently merge <code>seq1[i_start..i_end)</code> with <code>seq2[j_start..j_end)</code> and write the result directly to its output region, with no communication with other workers.</p>
<p>For a given <code>rank</code>, co_rank binary-searches for the unique <code>i</code> in the range <code>[max(0, rank-m), min(n, rank)]</code> such that the partition <code>(seq1[0..i), seq2[0..rank-i))</code> is valid. A partition is <em>valid</em> when:</p>
<ul>
<li>The last element of seq1's slice does not exceed the first unused element of <code>seq2</code>: <code>seq1[i-1] <= seq2[j]</code></li>
<li>The last element of seq2's slice does not exceed the first unused element of <code>seq1</code>: <code>seq2[j-1] <= seq1[i]</code></li>
</ul>
<p>Because both sequences are sorted, as <code>i</code> increases:</p><ul>
<li><code>seq1[i-1]</code> increases (moving right in <code>seq1</code>)</li>
<li><code>seq2[j-1]</code> decreases (moving left in <code>seq2</code>, since <code>j = rank - i</code> decreases)</li>
</ul>
<p>This means the condition <code>seq2</code>[j-1] <= <code>seq1</code>[i] transitions from <code>false</code> to <code>true</code> exactly once — making binary search applicable. The algorithm needs to check only one condition per iteration:</p>
<ul>
<li>If <code>seq2</code>[j-1] > <code>seq1</code>[i]: <code>i</code> is too large -> <code>high</code> = i</li>
<li>Otherwise: <code>i</code> is not large enough -> <code>low</code> = i + 1</li>
</ul>
<p>The figure below shows two iterations of the binary search for <code>rank=5</code> on sequences <code>seq1=[1,3,5,7,9,11]</code> and <code>seq2=[2,4,6,8,10,12]</code>:</p>
<p>The search converges to <code>i=3</code>, <code>j=2</code>: the first 5 merged elements consist of <code>seq1[0,3)=[1,3,5]</code> and <code>seq2[0,2)=[2,4]</code>, which interleave to <code>[1,2,3,4,5]</code>.</p>
<p>Unlike <aclass="el" href="classtf_1_1FlowBuilder.html#a597d2cceaf2a2598a3c4b9f742b0aacc" title="constructs an STL-styled parallel-for task">tf::Taskflow::for_each</a>, where users can configure a partitioner to adapt to unequal per-element costs, <code>std::merge</code> on a chunk of size <code>K</code> always costs <code>O(K)</code> regardless of the data values. There is little load imbalance to mitigate. As a result, <aclass="el" href="classtf_1_1FlowBuilder.html#adba094978bb2c038163e0b1b18141efa" title="merges two sorted ranges into a single sorted output using the std::less comparator">tf::Taskflow::merge</a> always adopts static partitioning, i.e., <code>W</code> chunks of size <code>N/W</code> and one per worker. which is always the optimal strategy for parallel merge. </p>
</div></div><!-- contents -->
</div><!-- PageDoc -->
</div><!-- doc-content -->
<!-- HTML footer for doxygen 1.13.1-->
<!-- start footer part -->
<divid="nav-path" class="navpath"><!-- id is needed for treeview function! -->