I have very large sorted array, stored on the disk.I can random access any element.I want to make it level-ordered in order to speed up binary search there. The idea is borrowed from:http://bannalia.blogspot.bg/2015/06/cache-friendly-binary-search.htmlIf I do this way, I believe I will be able to utilize the disk cache much better.However I do not see easy way to create level-ordered without using queue. Because the data is immutable, I do not need fast solution.Any ideas will be appreciated.
reordering sorted array to level-order array without queue
array;binary tree
Reorder can be done in lame way, e.g. print out level by level.I was unable to remove the recursion, but it does not need a queue.Also because we are working with an array, we do not need to touch it more that N times - e.g. we touch every element only once.Here are conceptual implementation that list only first few levels, but the idea is clear.Implementation in C++, but C would be almost the similar.#include <cstdio>void reorder(size_t const start, size_t const end, size_t const level, size_t const clevel = 0){    if (start >= end){        printf(NULL\n);        return;    }    size_t const mid = start + ((end - start) >> 1);    if (clevel == level){        // here we touch the array        printf(%zu\n, mid);        return;    }    reorder(start,   mid, level, clevel + 1);    reorder(mid + 1, end, level, clevel + 1);}void reorder(size_t const size, size_t const maxLevels){    for(size_t level = 0; level < maxLevels; ++level)        reorder(0, size, level);}int main(){    reorder(20, 4);}Here is additional example:https://gist.github.com/anonymous/c5890330f69402c2ef637055070a5ad2