qutil_mergesort

SYNOPSIS

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

       void
       qutil_qsort(qthread_t *me, double *array, size_t length);

       void
       qutil_mergesort(qthread_t *me, double *array, size_t length);

DESCRIPTION

       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-con-
       quer 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  primar-
       ily as a proof of concept rather than as a useful alternative.)

       The parallelism in these sorts is NOT limited by the futurelib resource
       restrictions, because of the divide-and-conquer trees in  both.  Future
       implementations may use the futurelib if and when futurelib is reimple-
       mented to allow forward progress without exceeding memory  restrictions
       (significantly)  even  when  there  are  an  extremely  large number of
       futures attempting to spawn new futures.

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

SEE ALSO

       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)



libqthread                         MAY 2007                     qutil_qsort(3)