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 algorithm must be comparison based.

Default Input Distributions

The distributions are as follows:

• Double-precision floating-point numbers generated uniformly at random from the range [0:1].
  Should be generated with:
  randomSeq -t double <n> <filename>

• Double-precision floating-point numbers generated at random with repeats appearing in an exponential distribution.
  Should be generated with:
  exptSeq -t double <n> <filename>

• Double-precision floating-point numbers from an almost-sorted distribution.
  Should be generated with:
  almostSortedSeq -t double <n> <filename>

• Pairs of double-precision floating-point numbers each generated uniformly at random from the range [0:1]. To be sorted on just the first element of the pair.
  Should be generated with:
  randomSeq -t double <n> <tmpfile>
addDataSeq -t double <tmpfile> <filename>

• Strings from a tri-gram distribution, as generated by the generator
  trigramSeq <n> <filename>

The large size is n = 100 million, and the small size is n = 10 million.

Input and Output File Formats

The input and output data need to be in the sequence file format, both with the same element type, which can be pairs.

The output file must be in sorted order with respect to the given comparison function.