The code of this tar file describes the implementation of the paper
``Probabilistic Integer Sorting'' by A.V.Gerbessiotis and C.J.Siniolakis.
Algorithm names refer to the algorithm of that paper.

What to do.
1. If you want to install BSPlib for accurate timings
   grad BSPlinux.tar or BSPsun.tar and tar xvf them in an appropriate
   directory. Do not forget to set path appropriately, eg.
   set path=(~/BSP/bin $path)
   if you tar xvf the .tar file at the top of your home directorty.
   In tcsh do in addition a rehash, and test if everyhing is ok by doing a
   bspcc. If you donot get a command not found you are done.
   BSPlinux was compiled under Red Hat Linux 9.0 and BSPsun.tar under Solaris 2.8 on
   an Ultra 10.

2. Alternatively, start from scratch tar xvf the v1.4_bsplib_toolset.tar version of
   BSPlib supplied (observe copyright notices), cd to the created BSP directory and do
   % ./configure
   % make 
   % make install
   Since you install a uniprocessor configuration, choose your architecture,
   SHMEM_SYSV, and p=1 in the questions asked by ./configure.

3. If you want to avoid steps 1 and 2 do the following
   a. Go to the Makefile and copy the first three lines after the next three
      (i.e. disable bspcc and enable gcc). Note if you use anoth C compiler
      replace gcc there.
   b. Go to the bsp1.h header file
      i. define ALEX by placing #define ALEX after #undef ALEX
      and hopefully you will be getting clock() timings instead of bsp_time() ones.

4. How to compile.
   % make all

5. How to change default run-time options. This affect the functions implemented
   i.e. Hybrid-Sort, Radix-Sort, and RS-Sort (our algorithm) in files
        hybrid.c     yyr.c       and rs_seq.c

   a. Edit bsp1.h
      i.  Set SELEM to string length; the length of the strings to be sorted.

6. How to change default options used for testing purposes in the yyhyb.c, yyr.c
   yyrs.c and yyqs.c for Hybrid-Sort, Radix-Sort, RS-Sort, and Qsort.
   b. Edit bsp1.h
      i.  Set N to minimum sort size (default 64)
    iii.  Make IT equal to 3 for testing problem sizes 64, 4096, 262144.
     iv.  If you want to run our algorithms on other problem sizes BE CAREFUL!

          You need to edit the corresponding yy*.c file and change the NN[..] array
          and the corresponding nm[] array.

          In general if each string is randomly distributed in 0...range-1 
          then NN[i] must be equal to range ** nm[i]  (**=exponentiation).
          For example if nm[i] = 1 or 2 or 3 and range=64 problem size
                      can be    64,4096 and 262144 respectively.

          It is imperative that you use these settings for HybridSort.
          RS-Sort works for larger values of nm[i]. For example for NN=262144
          you can try 3,4,5. If something goes wrong with sorting you will get
          an error message in execution time.

          Why so?
          Say N=262144. N random integers in the range 0..N-1 require lg(N) bits
          to represent each one i.e. 18 bits. One way to do so is filling 2 bytes
          with random bits and a fraction of a third byte. Another way is to
          fill each byte with 6 random bits (least significant ones). We thus
          fill each character with values in the range 0..range-1 with range=64.
          If we print them (in ASCII rather than hexadecimal) and we want to avoid
          Control characters we make offset=48.

7. How to run
   bsprun -npes 1 ../yyhyb 40 262144 64 48
40: disregard it. The value of SELEM in bsp1.h is used instead.
262144: This is an indicator. Make sure that IT is set to 3; otherwise if IT inbsp1.h
        is set to 4 something will crash!
64    : range acceptable value 0..255
48    : offset for printing purposes of the strings (0...255)
        Note range+offset <255

        Acceptable pairs.
        Try 64 48, 128 0 (but do not try to print anything as char!), 256 0.

8. If you get an error in output.
   Recheck steps 1-7 above.
9. Something crashes
   Go to step 8.
