I currently have a custom written Quicksort algorithm. But I thought I'd ask for someone to look over it, because there is at least one thing I am unsure of.

The code passes all the tests I have for it, but I cannot say if it's right or not.

The question is: which of these checks are required and which ones are not? I have commented out a great deal, and like I mentioned, it passes all my tests, but that doesn't mean it will always pass all tests, so...

Another thing is that I tried to parallellize the algorithm, but it turned out to be

*slower*. Not quite sure why. Perhaps someone has some suggestions or ideas...

Code:

`template<template<typename> class PivotType, typename RandomIt>`

void _Quicksort(RandomIt begin, RandomIt end, int Threads)

{

if (end - begin <= 1)

return;

RandomIt pivot = PivotType<RandomIt>::GetPivot(begin, end); // Gets the pivot

RandomIt left = begin, right = end - 2;

std::iter_swap(pivot, end - 1); // Swaps the two values pointed by the two iterators

pivot = end - 1;

//while (/*left <= right && *//*right >= begin && *//*left < end*/1)

for (;;)

{

while (*left < *pivot /*&& *//*left <= right && *//*left < end*/) ++left;

while (*right > *pivot /*&& right >= left && */&& right > begin) --right;

if (left > right) break;

std::iter_swap(left, right);

if (right == begin || left == end - 1) break;

/*if (left < end) */++left;

/*if (right > begin) */--right;

}

std::iter_swap(left, pivot);

//boost::thread* pThreads[2] = { NULL, NULL };

//if (Threads-- > 0)

//pThreads[0] = new boost::thread(boost::bind(&_Quicksort<PivotType, RandomIt>, begin, left, 0));

//else

Quicksort<PivotType>(begin, left);

//if (Threads-- > 0)

//pThreads[1] = new boost::thread(boost::bind(&_Quicksort<PivotType, RandomIt>, left + 1, end, 0));

//else

Quicksort<PivotType>(left + 1, end);

//if (pThreads[0]) pThreads[0]->join();

//if (pThreads[1]) pThreads[1]->join();

//Quicksort<PivotType>(begin, left);

//Quicksort<PivotType>(left + 1, end);

}