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 beslower. 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); }