<p>We can get a Theta(n log n)-time algorithm for 1 and a linear time algorithm for 2 and 3 as follows. For 1, we sort and apply 2. For 2, we use an inverse <a href="https://en.wikipedia.org/wiki/Faro_shuffle" rel="nofollow noreferrer">Faro shuffle</a> and a rotation to get the leaves to the end of the array, then "recurse" (tail recursion, so it's actually just a for loop) on the subtree with the leaves removed. For 3, we do the inverse steps of 2 in reverse order.</p>

<p>The C++ code below uses a Theta(n log n) Faro shuffle/inverse shuffle algorithm because it's easier than <a href="https://arxiv.org/abs/0805.1598" rel="nofollow noreferrer">Peiyush Jain's algorithm</a>. Note that Peiyush's algorithm may not be faster on real hardware for any realistic value of n due its poor cache utilization.</p>

<p>I have tested the code below on literally one input. You are hereby warned.</p>

<pre><code>#include &lt;algorithm&gt;
#include &lt;cassert&gt;
#include &lt;iostream&gt;
#include &lt;iterator&gt;
#include &lt;numeric&gt;
#include &lt;vector&gt;

namespace {

// Transforms [a0 b0 a1 b1 ... an-1 bn-1 an] to [a0 a1 ... an b0 b1 ... bn-1]
// and returns an iterator to b0. The running time is Theta(n log n). If you're
// feeling ambitious, you could try Peiyush Jain's linear-time algorithm.
template &lt;typename RandomAccessIterator&gt;
RandomAccessIterator InvertFaroShuffle(RandomAccessIterator first,
                                       RandomAccessIterator last) {
  using Index =
      typename std::iterator_traits&lt;RandomAccessIterator&gt;::difference_type;
  Index size = last - first;
  assert((size &amp; 1) == 1);
  if (size == 1) {
    return last;
  }
  RandomAccessIterator middle = first + (((size + 1) &gt;&gt; 2) &lt;&lt; 1);
  return std::rotate(InvertFaroShuffle(first, middle - 1), middle,
                     InvertFaroShuffle(middle, last));
}

// Theta(n log n)-time algorithm for #2.
template &lt;typename RandomAccessIterator&gt;
void SortedToLevelOrder(RandomAccessIterator first, RandomAccessIterator last) {
  using Index =
      typename std::iterator_traits&lt;RandomAccessIterator&gt;::difference_type;
  Index size = last - first;
  if (size &lt;= 1) {
    return;
  }
  unsigned height = 1;
  while ((Index{2} &lt;&lt; height) - 1 &lt; size) {
    height++;
  }
  for (unsigned level = height; level &gt; 0; level--) {
    Index effective_size = std::min((Index{2} &lt;&lt; level) - 1, size);
    Index leaf_count =
        std::min(Index{1} &lt;&lt; level, size - ((Index{1} &lt;&lt; level) - 1));
    InvertFaroShuffle(first, first + 2 * leaf_count - 1);
    std::rotate(first, first + leaf_count, first + effective_size);
  }
}

// Theta(n log n)-time algorithm for #1.
template &lt;typename RandomAccessIterator&gt;
void UnsortedToLevelOrder(RandomAccessIterator first,
                          RandomAccessIterator last) {
  std::sort(first, last);
  SortedToLevelOrder(first, last);
}

// Transforms [a0 a1 ... an b0 b1 ... bn-1] to [a0 b0 a1 b1 ... an-1 bn-1 an].
// The running time is Theta(n log n). If you're feeling ambitious, you could
// try Peiyush Jain's linear-time algorithm.
template &lt;typename RandomAccessIterator&gt;
void FaroShuffle(RandomAccessIterator first, RandomAccessIterator last) {
  using Index =
      typename std::iterator_traits&lt;RandomAccessIterator&gt;::difference_type;
  Index size = last - first;
  assert((size &amp; 1) == 1);
  if (size == 1) {
    return;
  }
  Index half = (size + 1) &gt;&gt; 1;
  RandomAccessIterator middle = first + half;
  Index quarter = half &gt;&gt; 1;
  middle = std::rotate(first + quarter, middle, middle + quarter);
  FaroShuffle(first, middle - 1);
  FaroShuffle(middle, last);
}

// Theta(n log n)-time algorithm for #3.
template &lt;typename RandomAccessIterator&gt;
void LevelOrderToSorted(RandomAccessIterator first, RandomAccessIterator last) {
  using Index =
      typename std::iterator_traits&lt;RandomAccessIterator&gt;::difference_type;
  Index size = last - first;
  if (size &lt;= 1) {
    return;
  }
  unsigned height = 1;
  while ((Index{2} &lt;&lt; height) - 1 &lt; size) {
    height++;
  }
  for (unsigned level = 1; level &lt; height + 1; level++) {
    Index effective_size = std::min((Index{2} &lt;&lt; level) - 1, size);
    Index leaf_count =
        std::min(Index{1} &lt;&lt; level, size - ((Index{1} &lt;&lt; level) - 1));
    std::rotate(first, first + (effective_size - leaf_count),
                first + effective_size);
    FaroShuffle(first, first + 2 * leaf_count - 1);
  }
}

void PrintList(const std::vector&lt;int&gt;&amp; list) {
  for (int elem : list) {
    std::cout &lt;&lt; ' ' &lt;&lt; elem;
  }
  std::cout &lt;&lt; '\n';
}

}  // namespace

int main() {
  std::vector&lt;int&gt; list(10);
  std::iota(list.begin(), list.end(), 0);
  PrintList(list);
  SortedToLevelOrder(list.begin(), list.end());
  PrintList(list);
  LevelOrderToSorted(list.begin(), list.end());
  PrintList(list);
}
</code></pre>
Algorithms for converting from complete-binary-search-tree order to sorted order and vice versa
<p>This question is similar to <a href="https://stackoverflow.com/questions/36419760/sorted-list-to-complete-bst-array-representation">Sorted list to complete BST array representation</a> but perhaps more specifically focused. This question could be used to solve <a href="https://stackoverflow.com/questions/34835192/inserting-node-dynamically-in-complete-binary-search-tree">Inserting node dynamically in Complete Binary Search Tree</a>.</p>

<p>Consider a <a href="http://web.cecs.pdx.edu/~sheard/course/Cs163/Doc/FullvsComplete.html" rel="nofollow noreferrer">complete binary tree</a> represented in memory as a contiguous array <code>a[0..n)</code>, where element <code>a[0]</code> is the root of the tree, and for any node <code>a[i]</code>, it has left child <code>a[2*i+1]</code> and right child <code>a[2*i+2]</code> (if those indices are less than <code>n</code>).</p>

<p>C++ programmers will be familiar with this representation because it's used by <a href="https://en.cppreference.com/w/cpp/algorithm/make_heap" rel="nofollow noreferrer"><code>std::make_heap</code></a>. <code>std::make_heap(a, a+n)</code> takes an unsorted array (which can be viewed as an unsorted complete binary tree) and permutes its elements (which can be viewed as tree rotations) to turn the tree into a complete binary <a href="https://www.cs.cmu.edu/~adamchik/15-121/lectures/Binary%20Heaps/heaps.html" rel="nofollow noreferrer">heap</a> where each node's value is greater than either of its children. We say that the resulting array is in "max-heap order."</p>

<p>On the other hand, if each node's value is greater than its left child but less than its right child, then we say that the complete binary tree is a complete binary <em>search tree</em>. In this case let's say that the resulting array is in "level order."<sup>[1]</sup></p>

<p>Whereas there are many permissible "max-heap orders" for a given set of elements, each set of elements has only a single unique "level order."</p>

<p>The following vectors are in level order:</p>

<pre><code>std::vector&lt;int&gt; v1 = { 3, 1, 4, 0, 2 };

// corresponds to the complete binary search tree
//    3
//  1   4
// 0 2

std::vector&lt;int&gt; v2 = { 6, 3, 8, 1, 5, 7, 9, 0, 2, 4 };

// corresponds to the complete binary search tree
//        6
//    3       8
//  1   5   7   9
// 0 2 4
</code></pre>

<p>What I'm looking for is a family of efficient algorithms for:</p>

<ol>
<li>permuting an unsorted sequence into level order</li>
<li>permuting a sorted sequence into level order</li>
<li>permuting a level-order sequence into sorted order</li>
</ol>

<p>When I say <em>efficient</em>, I mean algorithms that work without deep recursion, without dynamic memory allocation, and without temporary arrays. I already know that the permutation cannot be done particularly quickly; I'd hope for O(n lg n).</p>

<p>Notice that parts 2 and 3 are basically asking to come up with a mapping <code>OldIndex -&gt; NewIndex</code>; once you have such a function, you can do the permutation in-place using <a href="https://stackoverflow.com/a/54735864/1424877">one of these algorithms</a>.</p>

<p>Part 1 is asking for the implementation of <code>nonstd::make_searchtree</code> by analogy to <a href="https://en.cppreference.com/w/cpp/algorithm/make_heap" rel="nofollow noreferrer"><code>std::make_heap</code></a>. Part 3 is asking for the implementation of <code>nonstd::sort_searchtree</code> by analogy to <a href="https://en.cppreference.com/w/cpp/algorithm/sort_heap" rel="nofollow noreferrer"><code>std::sort_heap</code></a>.</p>

<hr>

<p>[1] — I basically made up this term "level order." If you know a more widely recognized academic term for this ordering, please leave a comment!</p>