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.