# NAG Library Function Document

## 1Purpose

nag_quicksort (m01csc) rearranges a vector of arbitrary type objects into ascending or descending order.

## 2Specification

 #include #include
void  nag_quicksort (Pointer vec, size_t n, size_t size, ptrdiff_t stride,
 Integer (*compare)(const Nag_Pointer a, const Nag_Pointer b),
Nag_SortOrder order, NagError *fail)

## 3Description

nag_quicksort (m01csc) sorts a set of $n$ data objects of arbitrary type, which are stored in the elements of an array at intervals of length stride. The function may be used to sort a column of a two-dimensional array. Either ascending or descending sort order may be specified.
nag_quicksort (m01csc) is based on Singleton's implementation of the ‘median-of-three’ Quicksort algorithm, Singleton (1969), but with two additional modifications. First, small subfiles are sorted by an insertion sort on a separate final pass, 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]$Pointer Input/Output
On entry: the array of objects to be sorted.
On exit: the objects rearranged into sorted order.
2:    $\mathbf{n}$size_tInput
On entry: the number, $n$, of objects to be sorted.
Constraint: $0\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{size}$size_tInput
On entry: the size of each object to be sorted.
Constraint: $1\le {\mathbf{size}}\le p$, where $p$ is an implementation-dependent value for the maximum size_t size on the system, divided by n if n is positive.
4:    $\mathbf{stride}$ptrdiff_tInput
On entry: the increment between data items in vec to be sorted.
Note: if stride is positive, vec should point at the first data object; otherwise vec should point at the last data object.
Constraint: ${\mathbf{size}}\le \left|{\mathbf{stride}}\right|\le p$, where $p$ is an implementation-dependent value for the maximum size_t size on the system, divided by n if n is positive.
5:    $\mathbf{compare}$function, supplied by the userExternal Function
nag_quicksort (m01csc) compares two data objects. If its arguments are pointers to a structure, this function must allow for the offset of the data field in the structure (if it is not the first).
The function must return:
 $-1$ if the first data field is less than the second, $\phantom{-}0$ if the first data field is equal to the second, $\phantom{-}1$ if the first data field is greater than the second.
The specification of compare is:
 Integer compare (const Nag_Pointer a, const Nag_Pointer b)
1:    $\mathbf{a}$const Nag_Pointer Input
On entry: the first data field.
2:    $\mathbf{b}$const Nag_Pointer Input
On entry: the second data field.
6:    $\mathbf{order}$Nag_SortOrderInput
On entry: specifies whether the array is to be sorted into ascending or descending order.
Constraint: ${\mathbf{order}}=\mathrm{Nag_Ascending}$ or $\mathrm{Nag_Descending}$.
7:    $\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

NE_2_INT_ARG_LT
On entry, $\left|{\mathbf{stride}}\right|=〈\mathit{\text{value}}〉$ while ${\mathbf{size}}=〈\mathit{\text{value}}〉$. These arguments must satisfy $\left|{\mathbf{stride}}\right|\ge {\mathbf{size}}$.
NE_ALLOC_FAIL
Dynamic memory allocation failed.
On entry, argument order had an illegal value.
NE_INT_ARG_GT
On entry, $\left|{\mathbf{stride}}\right|=〈\mathit{\text{value}}〉$.
Constraint: $\left|{\mathbf{stride}}\right|\le 〈\mathit{\text{value}}〉$, an implementation-dependent size that is printed in the error message.
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.
On entry, ${\mathbf{size}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{size}}\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 0$.
On entry, ${\mathbf{size}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{size}}\ge 1$.

Not applicable.

## 8Parallelism and Performance

nag_quicksort (m01csc) 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 two-dimensional array of numbers and sorts the second column into ascending order.

### 10.1Program Text

Program Text (m01csce.c)

### 10.2Program Data

Program Data (m01csce.d)

### 10.3Program Results

Program Results (m01csce.r)

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