Problem Based Benchmark Suite (2020)

Comparison Sort (SORT):

Given a sequence of elements of any (uniform) type and a comparison function over the elements, sort the elements into ascending order. The elements consists of a key and possible auxiliary data, and the comparison function must define a total order over the keys. The sort need not be stable. The code must not take advantage of the specific type beyond the comparison function.

Input and Output File Formats

The input and output data need to be in the sequence file format, both with the same element type. The output file must be in sorted order with respect to the given comparison function.

Default Input Distributions

Each distribution should be run for n=10,000,000. Currently none of the inputs use auxiliary data. The weight of each input for the purpose of reporting average times is given in parentheses.

• (1) Double precision floating point numbers generated uniformly at random from the range [0:1].

  randomSeq -t double <n> <filename>

• (1) Double precision floating point numbers generated at random with repeats appearing in an exponential distribution.

  exptSeq -t double <n> <filename>

• (1) Double precision floating point numbers from an almost-sorted distribution.

  almostSortedSeq -t double <n> <filename>

• (3) Strings from a tri-gram distribution.

  trigramSeq <n> <filename>

• (3) Strings from tri-gram distribution, but order randomized after allocation. In particular after the data is read in, the pointers to the strings have to be randomly shuffled (the shuffling should not be included in timing). The purpose of this test is to see how the sort does when strings are not allocated adjacently with respect to the input pointers.

  trigramSeq <n> <filename>