Sorting for search by monotomy Statement

Given N distinct integers, output them in order such that


for any integer J from 2 to N,


for any K>0 obtainable by dividing J by 2 (rounding down) at least one time,


the Jth integer output is larger than the Kth if and only if the division by 2 that gave K (i.e., the last division) divided an odd integer.




Note: this is for one-based index, as in common language, because it makes the statement less hairy. The motivating code below uses zero-based indexes.

This is a code golf. Output is a list of integers.

Example

Given the first 10 primes (in any order), the output must be in this order

 17  7  23  3  13  19  29  2  5  11 

which, when rewritten as a binary tree, gives:

                 17
         /---------------\
        7                23
    /-------\         /------\
   3        13       19      29
  /-\      /
 2   5    11


Note: when walking up in this tree towards its root, the parent is obtained by dividing the (one-based) index by two. The statement's "odd" and "larger" correspond to node at index J being compared to one of it's ancestor node at index K situated on the left and above.

Motivation

This allows search in a static list by monotomy, simpler and typically faster than dichotomy.

// Search t in table *p of length n (with n&lt;=MAX_INT/2 and n&gt;=0)
// Returns the index (zero-based), or -1 for not found
// Assumes table *p is in monotomic order (see below)
int monotomy(const int *p, int n, int t) {
  int j;
  for( j = 0; j&lt;n; j += (p[j]&lt;t)+j+1 )
    if( p[j]==t )
      return j;
  return -1;
  }

// Return 1 iff table *p is in correct order for monotomy
// Table *p of length n is zero-based.
int monotomic(const int *p, int n) {
  int j,k,m;
  for( j = 2; j&lt;n; ++j)
    for ( m = k = j; (k /= 2)&gt;0; m = k)
      if ( (p[j-1]&gt;p[k-1]) != (m%2) )  // zero-based indexes
        return 0;                      // incorrect order
  return 1;                            //   correct order
  }

// monotomy demo
#include &lt;stdio.h&gt;
int main(void) {
  const int p[] = { 17, 7, 23, 3, 13, 19, 29, 2, 5, 11, };
  #define n (sizeof(p)/sizeof(*p))
  int t, i, j;
  printf("monotomic = %d\n", monotomic(p, n) );
  for( t = i = 0; t&lt;9999; ++t )
    if( ( j = monotomy(p, n, t) )&gt;=0 )
      printf( "%d\n", p[++i, j] );
  if ( i!=n )
    printf("Incorrect\n");
  return 0;
  }
Jelly, 11 9 bytes

JBÇṙ€1ỤỤịṢ


Try it online! Explanation:

J           Create a range 1-(length of input array).
 B          Convert all the elements to binary.
  ṙ€1       Rotate each element left by 1.
     ỤỤ     Find each element's position within the sorted list.
       ịṢ   Apply that permutation to the sort of the input.