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: $1 \leq n \leq MAX_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

NE_BAD_PARAM: On entry, order had an illegal value.
NE_INT_ARG_GT: On entry, $n = ⟨ value ⟩$ .
Constraint: $n \leq ⟨ value ⟩$ , an implementation-dependent size that is printed in the error message.
NE_INT_ARG_LT: On entry, $n = ⟨ value ⟩$ .
Constraint: $n \geq 1$ .

7 Accuracy

Not applicable.

8 Parallelism and Performance

Background information to multithreading can be found in the Multithreading documentation.

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.

m01ca: FL CL CPP AD PY MB

NAG CL Interfacem01cac (realvec_​sort)

▸▿ Contents

1 Purpose

2 Specification

3 Description

4 References

5 Arguments

6 Error Indicators and Warnings

7 Accuracy

8 Parallelism and Performance

9 Further Comments

10 Example

10.1 Program Text

10.2 Program Data

10.3 Program Results

NAG CL Interface
m01cac (realvec_sort)