QuickSort – быстрый алгоритм сортировки (в среднем O(n log n) обменов при упорядочении n элементов) разработан Чарльзом Хоаром.

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

void QSort(FPTYPE *a, long p, long q)
{
	FPTYPE x = a[(p + q) / 2];
	long i = p, j = q;
	
	do {
		while (a[i] < x) i++;
		while (x < a[j]) j--;
		if (i <= j)
		{
			SwapValues(a + i, a + j);
			i++;
			j--;
		}
	} while (i <= j);
	
	if (p < j) QSort(a, p, j);
	if (i < q) QSort(a, i, q);
}

Рассмотрим одну из простейших идей распараллеливания данного алгоритма. Разделим все элементы на равные порции и передадим каждому из процессов для выполнения последовательной сортировки. Далее процессы с нечетными нумерами посылают свой отсортированный кусок последовательности соседу слева и выключаются из работы. Четные процессы выполняют слияние двух отсортированных последовательностей.

void Merge(FPTYPE *a, FPTYPE *b, FPTYPE *result, long na, long nb)
{
	long i = 0, j = 0, k = 0;

	while (i < na && j < nb)
		result[k++] = (a[i] < b[j]) ? a[i++] : b[j++];

	while (i < na) result[k++] = a[i++];
	while (j < nb) result[k++] = b[j++];
}

Происходит перенумерация процессов. Алгоритм повторяется до тех пор, пока в работе не останется только один процесс, осуществивший последнее слияние.