# Analysis on comparisons in a heap-like sorting algorithm

I've stumbled a heap-like sorting algorithm on the Internet as followed:

$\\$

For convenience, given a list of $2^n \; (n \in \mathbb{N^*})$ distinct numbers to be sorted increasingly.

Step 1: From the list, build a $P$-tree (to be defined) satisfying the min-heap property (Willard Zhan points out that this is actually a binomial heap), which costs $2^n-1$ comparisons. Go to Step 2.

Step 2: The root of the tree is the minimum on the tree at this time. So, pop it out and have $T$ trees remained. If $T > 1$, go to Step 3. If $T = 1$, go to Step 2. Otherwise, stop.

Step 3: By comparing their roots, join 2 of the remaining trees into 1 tree. The joining is done as followed: the larger root will be another child of the smaller root. The choice of 2 trees is done as followed: choose 2 trees with the least numbers of root's children. Continue joining until there is only 1 tree remained. One joining costs $1$ comparison, the whole step costs $T - 1$ comparisons ($T$ is taken from the previous step). Go to Step 2.

$P$-trees are defined as followed: $P_0$ is the $1$-node tree. For all positive integer $m$, $P_m$ is the tree having exactly $m$ first-class subtrees $P_0, ..., P_{m-1}$.

$\\$

I don't know this algorithm's proper name (if any). So I can't find any analysis on it, especially on its number of comparisons. I post this Question to ask for help on its name, its analysis, or some sources to read about them.

• With the "infinity" node, I've managed to proof an upper bound: $\; \; \; n(2^n-2)+1$ comparisons. However, so far I have no meaningful lower bound or the tight upper bound. – Vincent J. Ruan Jan 26 '17 at 14:42
• I've proved a lower bound: $\; \; \; 2^{n+1}-3+\dfrac{(n-1)(n-2)}{2}$ comparisons. Despite having no tight bounds, for now, I'm satisfied with the analysis and suspending my effort. – Vincent J. Ruan Jan 26 '17 at 15:30