5 of 13 Hopefully correct

# Sorting for search by monotomy

## Statement

Given N distinct integers, output them in order such that, for any integer from 2 to N, for any K>0 obtained 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 started from an odd integer.

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

This is a code golf. Output shall be in decimal, with some separator. 2 to 99 non-negative distinct integers must be handled, regardless of initial order.

## 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 

This is correct since

• for J=2,
• for K=1 obtained by dividing the (even) J=2 by 2, the second output 7 is smaller than the first output 17
• and for J=3,
• for K=1 obtained by dividing the (odd) J=3 by 2, the third output 23 is larger than the first output 17
• and for J=4,
• for K=2 obtained by dividing the (even) J=4 by 2, the 4th output 3 is smaller than the second output 7
• and for J=5,
• for K=2 obtained by dividing the (odd) J=5 by 2, the 5th output 13 is larger than the second output 7
• and for K=1 obtained by further dividing the (even) previous K=2 by 2, said 5th output 13 is smaller than the first output 17
• and for J=6,
• for K=3 obtained by dividing the (even) J=6 by 2, the 6th output 19 is smaller than the third output 23
• and for K=1 obtained by further dividing the (odd) previous K=3 by 2, said 6th output 19 is larger than the first output 17
• and for J=7,
• for K=3 obtained by dividing the (odd) J=7 by 2, the 7th output 29 is larger than the 4th output 3
• and for K=1 obtained by further dividing the (odd) previous K=3 by 2, said 7th output 29 is larger than the first output 17
• and for J=8,
• for K=4 obtained by dividing the (even) J=8 by 2, the 8th output 2 is smaller than the 4th output 3
• and for K=2 obtained by further dividing the (even) previous K=4 by 2, said 8th output 2 is smaller than the second output 7
• and for K=1 obtained by further dividing the (odd) previous K=3 by 2, said 8th output 2 is smaller than the first output 17
• and for J=9,
• for K=4 obtained by dividing the (odd) J=9 by 2, the 9th output 5 is larger than the 4th output 3
• and for K=2 obtained by further dividing the (even) previous K=4 by 2, said 9th output 5 is smaller than the second output 7
• and for K=1 obtained by further dividing the (odd) previous K=3 by 2, said 9th output 5 is smaller than the first output 17
• and for J=10,
• for K=5 obtained by dividing the (even) J=10 by 2, the 10th output 11 is smaller than the 5th output 13
• and for K=2 obtained by further dividing the (odd) previous K=5 by 2, said 10th output 11 is larger than the second output 7
• and for K=1 obtained by further dividing the (odd) previous K=3 by 2, said 10th output 11 is smaller than the first output 17

## 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<=MAX_INT/2 and n>=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<n; j += (p[j]<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<n; ++j)
for ( m = k = j; (k /= 2)>0; m = k)
if ( (p[j-1]>p[k-1]) != (m%2) )
return 0; // incorrect order
return 1;       //   correct order
}

// monotomy demo
#include <stdio.h>
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<9999; ++t )
if( ( j = monotomy(p, n, t) )>=0 )
printf( "%d\n", p[++i, j] );
if ( i!=n )
printf("Incorrect\n");
return 0;
}