Добавь сортировку из данного кода: template<class T>
void radix_sort(vector<T> &data) {
  static_assert(numeric_limits<T>::is_integer &&
                !numeric_limits<T>::is_signed,
                "radix_sort only supports unsigned integer types");
  constexpr int word_bits = numeric_limits<T>::digits;

  // max_bits = floor(log n / 3)
  // num_groups = ceil(word_bits / max_bits)
  int max_bits = 1;
  while ((size_t(1) << (3 * (max_bits+1))) <= data.size()) {
    ++max_bits;
  }
  const int num_groups = (word_bits + max_bits - 1) / max_bits;

  // Temporary arrays.
  vector<size_t> count;
  vector<T> new_data(data.size());

  // Iterate over bit groups, starting from the least significant.
  for (int group = 0; group < num_groups; ++group) {
    // The current bit range.
    const int start = group * word_bits / num_groups;
    const int end = (group+1) * word_bits / num_groups;
    const T mask = (size_t(1) << (end - start)) - T(1);

    // Count the values in the current bit range.
    count.assign(size_t(1) << (end - start), 0);
    for (const T &x : data) ++count[(x >> start) & mask];

    // Compute prefix sums in count.
    size_t sum = 0;
    for (size_t &c : count) {
      size_t new_sum = sum + c;
      c = sum;
      sum = new_sum;
    }

    // Shuffle data elements.
    for (const T &x : data) {
      size_t &pos = count[(x >> start) & mask];
      new_data[pos++] = x;
    }

    // Move the data to the original array.
    data.swap(new_data);
  }
}
Сюда: 
#include <iostream>
#include <vector>
#include <ctime>

using namespace std;

template< class T >
void downHeap(vector<T>& a, long k, long n)
{
    T new_elem;
    long child;
    new_elem = a[k];

    while (k <= n / 2)
    {
        child = 2 * k;

        if (child < n && a[child] < a[child + 1])
            child++;
        if (new_elem >= a[child])
            break;
        a[k] = a[child];
        k = child;
    }
    a[k] = new_elem;
}

template<class T>
struct TreeNode {
    T data;
    TreeNode* left;
    TreeNode* right;

    TreeNode(T value) {
        data = value;
        left = nullptr;
        right = nullptr;
    }
};

template<class T>
void insert(TreeNode<T>*& root, T value) {
    if (root == nullptr) {
        root = new TreeNode<T>(value);
        return;
    }

    if (value < root->data) {
        insert(root->left, value);
    }
    else {
        insert(root->right, value);
    }
}

template<class T>
void inOrderTraversal(TreeNode<T>* root, vector<T>& sortedArray) {
    if (root == nullptr) {
        return;
    }

    inOrderTraversal(root->left, sortedArray);
    sortedArray.push_back(root->data);
    inOrderTraversal(root->right, sortedArray);
}

template<class T>
void binaryTreeSort(vector<T>& a) {
    TreeNode<T>* root = nullptr;

    for (const T& value : a) {
        insert(root, value);
    }

    a.clear();
    inOrderTraversal(root, a);

    for (int i = a.size() - 1; i >= 0; i--) {
        cout << " " << a[i];
    }
}


int main() {
    setlocale(LC_ALL, "Russian");
    int n;
    cout << "Введите размер массива" << endl;
    cin >> n;

    vector<int> A(n);
    vector<int> B(n);
    vector<int> C;

    for (int i = 0; i < n; i++) {
        A[i] = -10000 + rand() % 20001;
        B[i] = -10000 + rand() % 20001;
    }

    for (int i = 0; i < n; i++) {
        cout << " " << A[i];
    }

    cout << endl;

    for (int i = 0; i < n; i++) {
        cout << " " << B[i];
    }

    for (int i = 0; i < n; i++) {
        if (A[i] % 2 == 0) {
            C.push_back(A[i]);
        }
        if (B[i] % 2 != 0) {
            C.push_back(B[i]);
        }
    }

    cout << endl;

    for (int i = 0; i < C.size(); i++) {
        cout << " " << C[i];
    }

    cout << endl << "Бинарное дерево - 1" << endl;
    int flag;
    cin >> flag;
    clock_t start_time = clock();
    if (flag == 1) binaryTreeSort(C);
    clock_t end_time = clock();
    double duration = (static_cast<double>(end_time -
        start_time)) / CLOCKS_PER_SEC;
    cout << " Time: " << duration << "sec" << endl;

    return 0;
}