structural:expansion, linguistic:voice_change, information:filtering, linguistic:translation
Join-based

This approach can be applied to every sorted sequence data structure that supports efficient join- and split-operations. The general idea is to split I {\displaystyle I} and T {\displaystyle T} in multiple parts and perform the insertions on these parts in parallel.

Note that in Step 3 the constraints for splitting I {\displaystyle I} assure that in Step 5 the trees can be joined again and the resulting sequence is sorted.

The pseudo code shows a simple divide-and-conquer implementation of the join-based algorithm for bulk-insert.Both recursive calls can be executed in parallel.The join operation used here differs from the version explained in this article, instead join2 is used, which misses the second parameter k.