What is the fastest way to merge two B trees?

Given two B-trees of some order $m$ - $T_1,T_2$, such that $y > x$ for every pair $x \in T_1$ and $y \in T_2$.
What is the fastest way to create a new tree that is the union of both $T_1,T_2$?

My current solution is naive in a sense that I create an array and insert all $T_1$ elements, than all $T_2$ elements.
As a result I have a sorted array which I can create a new tree off of with a cost of $n \log n$

I'm thinking that there must be a better solution, something like the AVL merging question but I can't figure it out.

It is great that you have obtained a sorted array, which runs in $O(n)$ time.

Once we have $n$ elements in a sorted array, every kind of "nice" tree, that I know, can be built in $O(n)$. In particular, we can build a $B$-tree in $O(n)$ time.

Here is an example. Suppose the sorted array is $$[1, 2, 3, 4, 5, 6, 7,8,9,10,11,12,13,14,15,16,17]$$ and we want to build a $2$-$4$ $B$-tree. Split the array into groups of $2$ numbers, except that last group that could be $2$ or $3$ numbers.
$$\{1, 2\}, \{3, 4\}, \{5, 6\}, \{7,8\},\{9,10\}, \{11,12\}, \{13,14\}, \{15,16, 17\}.$$

Had the number of groups been an odd number, great. Otherwise, distribute the elements in the last group so that the number of groups becomes odd.

$$\{1, 2\}, \{3, 4\}, \{5, 6\}, \{7,8\},\{9,10\}, \{11,12, 13\}, \{14,15,16, 17\}.$$

Label the groups successively as $g_1, g_2, \cdots, g_7$. Let $g_1$ be the root of the tree. Let the left child of $g_i$ be $g_{2i}$ if $2i\le n$ and the right child of $g_i$ be $g_{2i+1}$ if $2i+1\le n$. Now we have a complete binary tree where

• each node contains at least 2 number, and

• each internal node has 2 children.

That means, it is a $2$-$4$ $B$-tree.

The example above should provide enough idea so that a full algorithm for general situations should not be too difficult to figure out.

StackExchange Computer Science Q#125055, answer score: 3