Как распараллелить алгоритм быстрой сортировки?

Question

[kill94]

Помогите распараллелить алгоритм быстрой сортировки

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

[Олег Цилюрик]

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

Comments

[kill94]

стек переполняется

[Oxoron]

kill94: Параллельте лишь первые 2-4-8-16 вызовов (сколько у вас ядер?).

[kill94]

4
как это делать?

Answer 2

[ToricSphere]

Почитайте про сортировку Бэтчера(Например,в Кнуте), составьте сортировочную сеть, а свой алгоритм используйте в качестве последовательного в этой сети.