NAG CL Interface
m01cac (realvec_​sort)

Settings help

CL Name Style:

1 Purpose

m01cac rearranges a vector of real numbers into ascending or descending order.

2 Specification

#include <nag.h>
void  m01cac (double vec[], size_t n, Nag_SortOrder order, NagError *fail)
The function may be called by the names: m01cac, nag_sort_realvec_sort or nag_double_sort.

3 Description

m01cac is based on Singleton's implementation of the ‘median-of-three’ Quicksort algorithm, see Singleton (1969), but with two additional modifications. First, small subfiles are sorted by an insertion sort on a separate final pass, see Sedgewick (1978). Second, if a subfile is partitioned into two very unbalanced subfiles, the larger of them is flagged for special treatment: before it is partitioned, its end-points are swapped with two random points within it; this makes the worst case behaviour extremely unlikely.

4 References

Maclaren N M (1985) Comput. J. 28 448
Sedgewick R (1978) Implementing Quicksort programs Comm. ACM 21 847–857
Singleton R C (1969) An efficient algorithm for sorting with minimal storage: Algorithm 347 Comm. ACM 12 185–187

5 Arguments

1: vec[n] double Input/Output
On entry: elements of vec must contain real values to be sorted.
On exit: these values are rearranged into sorted order.
2: n size_t Input
On entry: the length of vec.
Constraint: 1nMAX_LENGTH, where MAX_LENGTH is an implementation-dependent value for the maximum size of an array.
3: order Nag_SortOrder Input
On entry: specifies whether the array will be sorted into ascending or descending order.
Constraint: order=Nag_Ascending or Nag_Descending.
4: fail NagError * Input/Output
The NAG error argument (see Section 7 in the Introduction to the NAG Library CL Interface).

6 Error Indicators and Warnings

On entry, order had an illegal value.
On entry, n=value.
Constraint: nvalue, an implementation-dependent size that is printed in the error message.
On entry, n=value.
Constraint: n1.

7 Accuracy

Not applicable.

8 Parallelism and Performance

m01cac is not threaded in any implementation.

9 Further Comments

The average time taken by the function is approximately proportional to n log(n) . The worst case time is proportional to n 2 but this is extremely unlikely to occur.

10 Example

The example program reads a list of real numbers and sorts them into ascending order.

10.1 Program Text

Program Text (m01cace.c)

10.2 Program Data

Program Data (m01cace.d)

10.3 Program Results

Program Results (m01cace.r)