The motivation for building this library is speed with special emphasis on arrays of C numeric types. The usort libraries use a combination of strategies including bucket sort, radix sort, quicksort, and insertion sort. The speedups will vary depending on: size of the numeric type, size of the array, and computing hardware on which the test is conducted.

This directory contains a set of C language sorting functions. There are two primary subdirectories to look at:

usort - contains optimized sorting routines for each of the basic c numeric types. The "u" is for universal... where the universe refers to the set of basic c numeric types.

qsort - a general purpose quicksort routine.

To use the code, simply #include the appropriate function.

The quicksort library uses static definition of the comparison operator (by means of macros) in order to prevent dispatch overhead. It is intended for general use in addition to its inclusion within the usort stragegies.

For the usorts, the speedups range from 3x for 8 byte numbers to incredable 250x for 1 byte integers (which can be sorted using bucket sort).

I test this code on both 32 and 64 bit intel architectures. Below are complete comparisons of the usorts against the GNU lib C qsort straw man. Timings were on my TravelMate 8210, a 32 bit intel machine with Intel(R) Core2 T7200 @ 2.00GHz and 2 gigs of RAM..

Univeral Sort Functions (usort or ufunc sorters) are fast sorting
algorithms specicialized for each of the basic C numeric types
Comparison of ufunc sorters against GLIBC qsort baseline
u1 - unsigned char
s1 - signed char
u2 - unsigned short
s2 - signed short
u4 - unsigned int
s4 - signed int
f4 - 4 byte float
u8 - unsigned long long
s8 - signed long long
f8 - 8 byte float (double).
TESTING APP: u1
N usort (secs) GLIBC qsort (secs) x-fold speedup
8 0.0000013044 0.0000022476 1.72
128 0.0000062864 0.0000709979 11.29
1024 0.0000144427 0.0007754159 53.69
10000 0.0000603504 0.0096700000 160.23
100000 0.0005544242 0.1160923939 209.39
1000000 0.0055322222 1.3435174444 242.85
10000000 0.0555820000 15.2838325000 274.98
TESTING APP: s1
N usort (secs) GLIBC qsort (secs) x-fold speedup
8 0.0000013236 0.0000022590 1.71
128 0.0000068531 0.0000718443 10.48
1024 0.0000161011 0.0007739059 48.07
10000 0.0000992372 0.0097043173 97.79
100000 0.0009392525 0.1159364647 123.43
1000000 0.0093115555 1.3405086666 143.96
10000000 0.0932485000 15.2905350000 163.98
TESTING APP: u2
N usort (secs) GLIBC qsort (secs) x-fold speedup
8 0.0000013062 0.0000022378 1.71
128 0.0000059180 0.0000712432 12.04
1024 0.0000283789 0.0007730834 27.24
10000 0.0002274915 0.0098890911 43.47
100000 0.0029452828 0.1219671414 41.41
1000000 0.0308931111 1.4411857778 46.65
10000000 0.3222000001 16.3975955000 50.89
TESTING APP: s2
N usort (secs) GLIBC qsort (secs) x-fold speedup
8 0.0000013016 0.0000022453 1.72
128 0.0000060273 0.0000709950 11.78
1024 0.0000357520 0.0007743004 21.66
10000 0.0003068939 0.0099215435 32.33
100000 0.0032695051 0.1223466768 37.42
1000000 0.0272346667 1.4397441111 52.86
10000000 0.2881805000 16.3111720000 56.60
TESTING APP: u4
N usort (secs) GLIBC qsort (secs) x-fold speedup
8 0.0000013842 0.0000019156 1.38
128 0.0000145125 0.0000400612 2.76
1024 0.0000841047 0.0003913318 4.65
10000 0.0005056587 0.0047337638 9.36
100000 0.0052576566 0.0565568182 10.76
1000000 0.0739924445 0.6631011111 8.96
10000000 0.9818515000 7.6159215000 7.76
TESTING APP: s4
N usort (secs) GLIBC qsort (secs) x-fold speedup
8 0.0000013934 0.0000019018 1.36
128 0.0000148855 0.0000399955 2.69
1024 0.0000885389 0.0003940953 4.45
10000 0.0005386577 0.0047699309 8.86
100000 0.0056020303 0.0568531717 10.15
1000000 0.0724470000 0.6657777778 9.19
10000000 1.0124520000 7.6765220000 7.58
TESTING APP: f4
N usort (secs) GLIBC qsort (secs) x-fold speedup
8 0.0000013674 0.0000019814 1.45
128 0.0000189171 0.0000443792 2.35
1024 0.0001437735 0.0004537536 3.16
10000 0.0010609349 0.0054732893 5.16
100000 0.0103490303 0.0657784848 6.36
1000000 0.1114643333 0.7678498889 6.89
10000000 1.1413060001 8.8897940000 7.79
TESTING APP: u8
N usort (secs) GLIBC qsort (secs) x-fold speedup
8 0.0000014774 0.0000019841 1.34
128 0.0000180451 0.0000440726 2.44
1024 0.0002008706 0.0004311888 2.15
10000 0.0020998599 0.0050863193 2.42
100000 0.0190793838 0.0621567071 3.26
1000000 0.2457824444 0.7381691111 3.00
10000000 2.8299570000 8.5275200000 3.01
TESTING APP: s8
N usort (secs) GLIBC qsort (secs) x-fold speedup
8 0.0000014621 0.0000019779 1.35
128 0.0000186448 0.0000437078 2.34
1024 0.0002022761 0.0004321395 2.14
10000 0.0012153534 0.0051192613 4.21
100000 0.0122118182 0.0616136869 5.05
1000000 0.1933817778 0.7349713333 3.80
10000000 2.3513790000 8.5338990000 3.63
TESTING APP: f8
N usort (secs) GLIBC qsort (secs) x-fold speedup
8 0.0000013375 0.0000019670 1.47
128 0.0000154629 0.0000450866 2.92
1024 0.0001696976 0.0004562643 2.69
10000 0.0013682102 0.0055419099 4.05
100000 0.0136390101 0.0677483838 4.97
1000000 0.1982658889 0.7983115555 4.03
10000000 2.3578315001 9.2898030000 3.94