Test Setup
One method for verification of correctness is to compare algorithm implementations to STL sort for assurance of equivalent results, but that assumes STL sort is correct. To not rely on correctness of STL sort requires implementing a correctness test for sorting algorithms. Correctness requires that array[i] ≤ array[i+1] for all elements of the array, which is simple to check. Of course, comparison to results from STL sort would be a useful redundant verification. These two tests were used for all implemented routines, including Intel's IPP library routines. Boundary cases of the input arrays of size 0 and 1 were also tested.
The performance comparison setup was as follows:
- Visual Studio 2008, optimization project setting is set to optimize neither speed or size, and inline any suitable function.
- Intel Core 2 Duo CPU E8400 at 3 GHz (64 Kbytes L1 and 6 Mbytes L2 cache).
- 14-stage pipeline with 1,333 MHz front-side bus.
- 2 GB of system memory (dual-channel 64-bits per channel, 800 MHz DDR2).
- motherboard is DQ35JOE.
Random numbers were generated by using the following method for each element in the array:
// each call to rand() produces 15-bit random number.
unsigned long tmp = ((unsigned long)rand()) << 30 |
((unsigned long)rand())<< 15 |
((unsigned long)rand());
The arrays were all checked for percentage of unique values, which were all above 95% for arrays filled with 32-bit unsigned values. The range of min and max were also checked for each array, which were between 0 and near the max value for 32-bit unsigned numbers.
Performance was measured by always processing 100 million elements. When 10 element arrays were being measured, then 10 million of them were allocated. When 100 element arrays were being measured, then 1 million of them were allocated, and so on. A different random-number generator seed was used for each array, but the same seeds were used across all algorithms. Time-stamp was taken before sorting the 10 million arrays and also after. The average value across all arrays is the value reported.
