Inline QSORT() implementation

There's a qsort() routine defined in Standard C Library, which can be used to quickly sort an array of elements of some type, having comparison routine defined. The qsort algorithm is very fast (well, almost: various implementations are different from each other, and not every platform/OS have equally good implementation, some may perform slower than others). But if you want to sort a huge amount of data (like, eg, rbldnsd does), standard qsort() may be not a very good idea, and here's why:

This is where this implementation comes handy. First, it is based on qsort() as used in GNU LibC (glibc) library, which implements several optimizations for traditional (simplistic) algorithm, thus making it almost O(n) for all cases. And, this version is implemented as a macro, not as a routine which expects an address of comparison function, so the compiler can do its best to optimize resulting code. This makes the whole procedure alot faster than using qsort() -- for example, doing integer qsort (sorting array of integers) is almost 4 times faster than using qsort() routine from glibc.

The implementation consists of a single header file, qsort.h, which can be a part of any software package. See usage instructions and examples inside.

Alternatively there's a single .c file, qsort.c, which can be #include'd into your program at the appropriate place (where actual sorting should be done) -- again, see usage instructions inside the file.

The license is LGPL - the same as glibc implementation (which basically means you're free to use it in any project you like, but any changes in this file should be made public).

The code is adopted from glibc by Michael Tokarev, <mjt+qsort@corpit.ru>


Page last modified Mon, 28 Jan 2008 21:19:44 +0300 by mjt.

Return to my software page.