Как и для большинства алгоритмов сортировки, методика «быстрой» сортировки взята из повседневного опыта. Чтобы отсортировать большую стопку алфавитных карточек по именам, можно разбить ее на две меньшие стопки относительно какой-нибудь буквы, например K. Все имена, меньшие или равные K, идут в одну стопку, а остальные – в другую.

Данный алгоритм очень удачно подходит для распараллеливания. Меня заинтересовало, какой прирост к производительности будет, если использовать потоки.

Описание «быстрой» сортировки

Подробно о самой сортировке можно прочитать на том же rsdn. Тут коснусь пары основных моментов. Вообще, главное в данной сортировке, что после выбора опорного элемента, слева от него остаются все элементы меньше его, а справа большие. И далее происходит рекурсивный вызов функции сортировки для каждого подмассива. Идея в том, чтобы сортировку обеих частей провести в отдельных поток. Теоретически, в идеальном варианте, когда слева и справа одинаковое число элементов, создавая 2 потока на 2-х ядерном процессоре, скорость выполнения должна увеличиться на 100%.

Алгоритм сортировки

Реализация сортировки наивная, опорным элементом изначально всегда берётся серединный элемент массива. При ветвлении создание потоков для обеих веток не разумно, ибо затраты на создание потока под меньший подмассив превышают время выполнения сортировки подмассива. Можно улучшить алгоритм: создавать поток лишь для большего подмассива, а меньший обрабатывать в текущем потоке.

DWORD __stdcall SortMasP (LPVOID p)
{
	lpArrayParam Params = (lpArrayParam)p;
	if (Params->left>=Params->right) return 0;
	int left, right, supporting;
	int temp;
	int * mas;

	left=Params->left;
	right=Params->right;
	mas = Params->mas;
	supporting=(((lpArrayParam)p)->left+((lpArrayParam)p)->right)/2;

	while(Params->left<Params->right)
	{
		while ((Params->left<supporting)&amp;&amp;(mas[Params->left]<=mas[supporting]))
			Params->left++;   // Сдвиг левой границы
		while ((Params->right>supporting)&amp;&amp;(mas[Params->right]>=mas[supporting]))
			Params->right--;    // Сдвиг правой границы
		// Обмен граничных элементов
		Swap(&amp;mas[Params->left],&amp;mas[Params->right]);
		// Обновление индекса опорного элемента
		if (Params->left == supporting ) supporting = Params->right;
		else if (Params->right == supporting ) supporting = Params->left;
	}
	lpArrayParam Params1 = new ArrayParam;
	Params1->left=left;
	Params1->right=supporting-1;
	Params1->mas = mas;

	lpArrayParam Params2 = new ArrayParam;
	Params2->left=supporting+1;
	Params2->right=right;
	Params2->mas = mas;


	if(TCount<pc)
	{

		HANDLE  thr;
		InterlockedIncrement(&amp;TCount);


		if(Params2->right-Params2->left<Params1->right-Params1->left)
		{
			thr = CreateThread(0,0,(LPTHREAD_START_ROUTINE)SortMasP, Params1,0,0);
			SortMasP(Params2);
			WaitForSingleObject(thr,  INFINITE);
        }
		else
		{
			thr = CreateThread(0,0,(LPTHREAD_START_ROUTINE)SortMasP, Params2,0,0);
			SortMasP(Params1);
			WaitForSingleObject(thr,  INFINITE);
        }

		InterlockedDecrement(&amp;TCount);
		CloseHandle(thr);

	}
	else
	{
		SortMasP(Params1);
		SortMasP(Params2);
	}


	delete Params2;
	delete Params1;
	return 0;
}

Ну, и дополнительные функции/переменные, используемые в методе.

//обмен элементов
void Swap(int *a, int *b)
{
	int temp = *a; *a=*b; *b=temp;
}

DWORD GetProcessorCount()
{
	SYSTEM_INFO si;
	GetSystemInfo(&si);
    return si.dwNumberOfProcessors;

}

DWORD pc=GetProcessorCount(); //число процессоров

//структура для передачи параметров
typedef struct _ArrayParam
{
	int left;
	int right;
	int * mas;

} ArrayParam, *lpArrayParam;

LONG TCount = 0;	//количество созданных потоков

Результаты сравнения

Сравнение последовательной и параллельной сортировки производилось для различных размеров массивов. Для каждой размерности производилось 100 тестов. Тесты преимущество производились на 2-х ядерных машинах. ОС были разные: XP, Vista, Windows 7. Результаты на всех операционках не сильно отличаются.

Как видно, при использовании потоков происходит прирост производительности, когда элементов в массиве больше 50.000. Это объясняется тем, что на создание потоков и работы с их контекстами (при переключении происходит выгрузка в регистры, когда поток снова активен, загрузка), да и на создание потоков в принципе тратится не мало ресурсов. Поэтому эффект заметен лишь на массивах, оперирующих большим числом элементов.

Стоит сказать, что результаты приведены усреднённые. В единичных случаях бывает, что использование потоков ускоряют алгоритм на 80%.