I received e-mail with request to explain, why my template is faster than qsort() function. I think, it is
interesting question for everyone.
First, I explain quick sort algorithm. It is based on partitioning array in two parts, divided by element
called pivot. Pivot could be choose median value of the values from part of array going to be sorted, but it
is a big performance hit to look for median value. Therefore it is better choose value from middle of array.
After pivot is known, all values smaller than pivot is moved to the lower (left) part of array and bigger
values to upper (right) part of array (when array is sorting ascending). And then everything begins again, in
both parts of array separately, until whole array is sorted.
Sources for qsort() function you can find in \DevStudio\Vc\Crt\Src\Qsort.c (I installed Visual C++ 5.0 to
When I compared qsort() sources with my QuickSort() function template, I found:
1. qsort() is not recursive
Author(s) of qsort() uses their own stacks to remember borders of parts of array. It could be performance
hit (it needs more CPU clocks than recursive call of function).
2. qsort() is too complicated and too long
In the qsort() you can find plenty of comparisons and calculations. More comparisons & calculations =
more instructions = slower function. qsort() function copies more elements of array than it is necessary too.
Can not believe? Compare it:
while (pArr[j] < str) j++;
loguy += width;
} while (loguy <= hi && comp(loguy, lo) <= 0);
Above you can see parts from both functions. Both do the same thing.
You can find unnecessary copy operation too.
3. qsort uses 'goto'
I do not think, that 'goto' will produce slower code, but in qsort() function it is used on places, where
Pentium processors can not predict, which instructions will be executed, I think. So, it could decrease
4. optimization for speed and for processor
When you have your own code to compile, you can optimize it for speed and for specific processor. I can
say, it will bring much faster code every time. Well, when I rebuild my demo program without optimization for
speed, QuickSort() function template left still faster (try it) than qsort() function, but two times slower
than version optimized for speed.
So, if my QuickSort() function template and array template are not too fast for you, feel free use them.