Recursive Binary List Conversion

[MasterGberry]

Title may be a bit off, but I am having issues trying to form this last function. I created a simple sorting algorithm for a list of ints I have for a project, now the ints are from the min to max. I know the size and have a pointer to the beginning of the array. What I need to do is now re-order them as if they were being cut into a binary tree. So here is a list as my exmaple:

401, 414, 428, 431, 439, 444, 450, 456, 367, 372, 501, 515, 529, 554

They division on where to split is a ceiling function, so if we have an even number divided by 2 then we go up one, aka 14/2 = 8. If the number is odd then we use the ceiling again, aka 7/2 = 4.

The final list needs to be this:

577, 456, 431, 414, 401, 428, 444, 439, 450, 515, 472, 467, 501, 554

This is being inserted into a binary tree then. Any advice, examples, or anything is much appreciated. It's late, I can't seem to process this anymore, and I have been working on this project for at least 10 hours today. Not due for another week or so, but I am trying to stay ahead of my work and I really want to get this last part done after I spent so much time debugging :)

Thanks once again.

[mrnutty]

You can basically do a 'binary split adding the middle every split. I tried coding something real quick and here it is:

#include <iostream>
#include <cmath>
#include <iterator>
#include <vector>
using namespace std;


template<typename T, typename Result>
void _splitImpl(T begin, T end, Result& result);


template<typename RandomAccessIterator>
std::vector<int> binarySplit(RandomAccessIterator begin, RandomAccessIterator end){
    std::vector<int> result;
    _splitImpl(begin,end,result);    
    return result;
}

template<typename T, typename Result>
void _splitImpl(T begin, T end, Result& result){
    if(begin > end) return;
    else{
        size_t mid = std::distance(begin,end)/2;
        result.push_back( *(begin + mid) ); 
        _splitImpl( begin , begin + mid - 1, result);
        _splitImpl(begin + mid + 1, end , result);
    }
}
template<typename T>
void print(T begin, T end){
    while(begin != end){ cout << *begin << " "; ++begin; }
}
int main(){
    int a[] = {401, 414, 428, 431, 439, 444, 450, 456, 367, 372, 501, 515, 529, 554};
    const int size = sizeof(a)/sizeof(*a);
    print(a , a + size);
    std::vector<int> result = binarySplit(a , a + size);
    print(result.begin(), result.end());
}

That should get you going, but there is a bug there, a "off-by-one" bug which I'll leave for you to fix, because I need some sleep. Cheers!