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

Question

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

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;
            }
        }
    }
}

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