Openmp сортировка деревьев

Я сортирую массив, используя алгоритм сортировки дерева:

1. Построить дерево из массива.
2. Inorder пересекает дерево и записывает обратно в массив.

Серийная версия кода работает нормально, но я хочу попытаться улучшить производительность, используя openmp. Я знаю, что есть алгоритмы типа сортировки слиянием, которые больше подходят для параллелизма, но я все еще хочу попытаться решить эту проблему с помощью сортировки по дереву, если это возможно.

Я попытался реализовать обход inorder, как показано ниже, но он медленнее, чем оригинальная версия.

// Serial inorder traversal of binary tree
void inorder_v1(const tree* t, unsigned* arr, int &i) {
if(t == NULL)
return;
inorder_v1(t->left, arr, i);
arr[i++] = t->value;
inorder_v1(t->right, arr, i);
}

//Parallel inorder traversal of binary tree
void inorder_v2(const tree* t, unsigned* arr, int &i) {
if(t->left != NULL) {
#pragma omp task shared(i)
inorder_v2(t->left, arr, i);
}
#pragma omp taskwait

arr[i++] = t->value;

if(t->right != NULL) {
#pragma omp task shared(i)
inorder_v2(t->right, arr, i);
}
#pragma omp taskwait
}

Затем я попытался распараллелить построение дерева вместо этого, но это также было медленнее, чем оригинал, и это не всегда приводило к правильному дереву.

tree* t = (tree*)calloc(1, sizeof(tree));
t->value = arr[0];

#pragma omp parallel for
for(int i = 1; i < n; i++) {
tree *current = t; // Iterator
tree *parent = t; // Trailing iterator
tree *node = (tree*)calloc(1, sizeof(tree)); // Node to insert
node->value = arr[i];
bool flag = true;

// traverse the tree and find parent node of the value
while (flag) {
parent = current;
if (node->value < current->value)
current = current->left;
else
current = current->right;

#pragma omp critical
{
if(current == nullptr) {
// construct a new node and assign to appropriate parent pointer
if (node->value < parent->value)
parent->left = node;
else
parent->right = node;
flag = false;
}
}
}
}

Я новичок в параллельном программировании, поэтому любые предложения или советы о том, как решить эту проблему, будут с благодарностью.