qutil_qsort - Man Page

#include <qthread.h>
#include <qthread/qutil.h>

void
qutil_qsort (double *array, size_t length);

void
qutil_mergesort (double *array, size_t length);

These functions take as input an array of length numbers and sorts their values.

In qutil_qsort(), large amounts of parallelism is achieved by using a strided lagging-loop structure for the partitioning phases of the sort, and a tree structure (with a minimum leaf-size) for the divide-and-conquer phases of the sort. The design is based, partly, upon work done by CRAY for their MTA-threaded quicksort. For sufficiently small arrays or sub-arrays, the libc qsort() function is used.

In qutil_mergesort(), the parallelism is achieved solely from the obvious divide-and-conquer tree. The merge phases of the algorithm use an in-place merge rather than a lookaside merge. As a result, the merge phases are rather computationally intensive. (This sort exists primarily as a proof of concept rather than as a useful alternative.)

The result of the sort is an array in increasing order.

qutil_double_sum(3), qutil_double_mult(3), qutil_double_min(3), qutil_double_max(3), qutil_uint_sum(3), qutil_uint_mult(3), qutil_uint_min(3), qutil_uint_max(3), qutil_int_sum(3), qutil_int_mult(3), qutil_int_min(3), qutil_int_max(3), qsort(3)

qutil_double_max(3), qutil_double_min(3), qutil_double_mult(3), qutil_double_sum(3).