NAG Library Function Document

1Purpose

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

2Specification

 #include #include
 void nag_double_sort (double vec[], size_t n, Nag_SortOrder order, NagError *fail)

3Description

nag_double_sort (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.

4References

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

5Arguments

1:    $\mathbf{vec}\left[{\mathbf{n}}\right]$doubleInput/Output
On entry: elements of vec must contain real values to be sorted.
On exit: these values are rearranged into sorted order.
2:    $\mathbf{n}$size_tInput
On entry: the length of vec.
Constraint: $1\le {\mathbf{n}}\le \mathrm{MAX_LENGTH}$, where $\mathrm{MAX_LENGTH}$ is an implementation-dependent value for the maximum size of an array.
3:    $\mathbf{order}$Nag_SortOrderInput
On entry: specifies whether the array will be sorted into ascending or descending order.
Constraint: ${\mathbf{order}}=\mathrm{Nag_Ascending}$ or $\mathrm{Nag_Descending}$.
4:    $\mathbf{fail}$NagError *Input/Output
The NAG error argument (see Section 3.7 in How to Use the NAG Library and its Documentation).

6Error Indicators and Warnings

On entry, order had an illegal value.
NE_INT_ARG_GT
On entry, ${\mathbf{n}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{n}}\le 〈\mathit{\text{value}}〉$, an implementation-dependent size that is printed in the error message.
NE_INT_ARG_LT
On entry, ${\mathbf{n}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{n}}\ge 1$.

Not applicable.

8Parallelism and Performance

nag_double_sort (m01cac) is not threaded in any implementation.

The average time taken by the function is approximately proportional to $n\mathrm{log}\left(n\right)$. The worst case time is proportional to ${n}^{2}$ but this is extremely unlikely to occur.

10Example

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

10.1Program Text

Program Text (m01cace.c)

10.2Program Data

Program Data (m01cace.d)

10.3Program Results

Program Results (m01cace.r)

© The Numerical Algorithms Group Ltd, Oxford, UK. 2017