Использование OpenMP для распараллеливания быстрой сортировки

Question

Я пытаюсь использовать OpenMP для распараллеливания быстрой сортировки (для массивов с различными целыми числами). У меня уже есть рабочая реализация (я проверил вывод для нескольких потоков, и, кажется, работает). Проблема в том, что я не вижу никакого ускорения, даже для больших массивов, что приводит меня к мысли, что моя реализация не верна. Поскольку фактическая реализация верна, но параллелизм, по-видимому, не дает желаемого ускорения, я покажу только распараллеливание кода:

void parallel_randomized_quicksort(vector<int>& A, int start, int end){
  if ((end-start) is too small){
    run a serial sorting algorithm
  }else{
    pick a random pivot x and partition A around that pivot.
    k = index of x in A
    #pragma omp parallel
    {
      #pragma omp single nowait
      {
        parallel_randomized_quicksort(A,start,k-1);
      }
      #pragma omp single nowait
      {
        parallel_randomized_quicksort(A,k+1,end);
      }
    }
  }
}

Если это правильно, должно быть некоторое ускорение, так как левый и правый разделы могут повторяться параллельно, что является целью моего кода. Почему я не замечаю ускорение?

EDIT: Время выполнения измеряется с помощью:

double start_time = omp_get_wtime();
  parallel_randomized_quicksort(A,0,A.size()-1);
  double time = omp_get_wtime() - start_time;

Массивы являются различными целыми числами. Размеры массивов варьируются от 100 до 1000000. Времена в миллисекундах для меньших массивов и пара секунд для больших. Обычно, если размер массива меньше 32, я использую простой последовательный алгоритм, например сортировку вставкой.