How to parallelize quicksort algorithm?

Question

Parallel Computing

Help parallelize the quicksort algorithm

void QuickSort(string masStr[], long size)
{
  int l, r;
  int i, j;
  int lstack[MAXSTACK], rstack[MAXSTACK];
  int stackPos = 1;
  long middle;

  char pivot[MAX_LENGTH_STR + 1];
  string temp;
  lstack[1] = 0;
  rstack[1] = size - 1;

  do{
    l = lstack[stackPos];
    r = rstack[stackPos];
    stackPos--;
    do{
      middle = (l + r) >> 1;
      i = l; j = r;  strcpy(pivot, masStr[middle].c_str()); // Находим разделительный элемент в середине массива
      do{
        while (strcmp(masStr[i].c_str(), pivot)<0)
          i++; // Находим элемент  от левого индекса.
        while (strcmp(masStr[j].c_str(), pivot)>0)
          j--; // Находим элемент  от правого индекса.
        if (i <= j){
          temp = masStr[i];
          masStr[i] = masStr[j];
          masStr[j] = temp;
          i++;
          j--;
        }
      } while (i <= j);

      if (i < middle){
        if (i < r){
          stackPos++;
          lstack[stackPos] = i;
          rstack[stackPos] = r;
        }
        r = j;
      }
      else{
        if (j>l){
          stackPos++;
          lstack[stackPos] = l;
          rstack[stackPos] = j;
        }
        l = i;
      }
    } while (l < r);
  } while (stackPos != 0);
}

Answer 1

No one, of course, will begin to poke around in your heap of code.
But the general approach might be:
- Express quicksort recursively
- Decompose individual branches of recursion into parallel threads of execution.

Answer 2

Read about Batcher's sorting (For example, in Knuth), make a sorting network, and use your algorithm as a sequential one in this network.