Problem Based Benchmark Suite (2020)

Integer Sort (ISORT):

Sort fixed-length unsigned integer keys into ascending order with the ability to carry along fixed-length auxiliary data. The sort must be stable unless the benchmark is indicated with -U (ISORT-U).

Input and Output File Formats

The input and output should be in the sequence file format. The output file must be in sorted with respect to the integer values. If there is auxiliary data it must be included in the output and the sort must be stable unless indicated with -U.

Default Input Distributions

Each distribution should be run for n=10,000,000. The weights used for average time are given in parentheses.

• (1) Unsigned integers generated uniformly at random in the range [0:n).

  randomSeq -t int <n> <filename>

• (1) 32-bit unsigned integers generated at random with repeats appearing in an exponential distribution.

  exptSeq -t int <n> <filename>

• (1) Unsigned integers generated uniformly at random in the range [0:n) each with an auxiliary unsigned integer in the same range.

  randomSeq -t int <n> <tmpname>
  addDataSeq -t int <tmpname> <filename>
  

• (1) Unsigned integer keys generated uniformly at random in the range [0:256) each with an auxiliary unsigned integer in the range [0:n).

  randomSeq -t int -r 256 <n> <tmpname>
  addDataSeq -t int <tmpname> <filename>