/*
Revised 11 oct 1999:
No changes have been made to the code
only the comments have been extended.
Also, my address has changed:
Stefan Nilsson
KTH, Nada
SE-100 44 Stockholm
Sweden
http://www.nada.kth.se/~snilsson
*/
/*
This is an impelementation of an integers sorting algorithm that
sorts n word-sized integers in O(n log log n) worst-case time.
The algorithm was originally presented in the article:
A. Andersson, T. Hagerup, S. Nilsson, and R. Raman. Sorting
in linear time? In Proceedings of the 27th Annual ACM
Symposium on the Theory of Computing, pages 427-436, 1995.
A more complete discussion of the algorithm, the implementation
and a comparison with other well known sorting algorithms, both
radix sorting and comparison-based methods, can be found in:
S. Nilsson. Radix Sorting & Searching. PhD thesis, Department
of Computer Science, Lund University, 1996.
Both publications can be fetched from my homepage:
http://www.cs.hut.fi/~sni/
The code presented in this file has been tested with care but is
not guaranteed for any purpose. The writer does not offer any
warranties nor does he accept any liabilities with respect to
the code.
Stefan Nilsson, 26 oct 1996.
Laboratory of Information Processing Science
Helsinki University of Technology
*/
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <errno.h>
#define W 32 /* Word length, machine dependent */
typedef unsigned int word; /* W-bit word */
word Masks[5]; /* 5 = log_2(W) */
/* Utilities
*/