m01 Chapter Contents
m01 Chapter Introduction
NAG C Library Manual

# NAG Library Function Documentnag_stable_sort (m01ctc)

## 1  Purpose

nag_stable_sort (m01ctc) rearranges a vector of arbitrary type objects into ascending or descending order.

## 2  Specification

 #include #include
void  nag_stable_sort (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)

## 3  Description

nag_stable_sort (m01ctc) 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.
A stable sort is one which preserves the order of distinct data items that compare equal. This function uses nag_rank_sort (m01dsc), nag_make_indices (m01zac) and nag_reorder_vector (m01esc) in order to carry out a stable sort with the same specification as nag_quicksort (m01csc). nag_stable_sort (m01ctc) will be faster than nag_quicksort (m01csc) if the comparison function compare is slow or the data items are large. Internally a large amount of workspace may be required compared with nag_quicksort (m01csc).

## 4  References

Knuth D E (1973) The Art of Computer Programming (Volume 3) (2nd Edition) Addison–Wesley

## 5  Arguments

1:     vec[${\mathbf{n}}$]Pointer Input/Output
On entry: the array of objects to be sorted.
On exit: the objects rearranged into sorted order.
2:     nsize_tInput
On entry: the number $n$ of objects to be sorted.
Constraint: ${\mathbf{n}}\ge 0$.
3:     sizesize_tInput
On entry: the size of each object to be sorted.
Constraint: ${\mathbf{size}}\ge 1$.
4:     strideptrdiff_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: $\left|{\mathbf{stride}}\right|\ge {\mathbf{size}}$.
5:     comparefunction, supplied by the userExternal Function
nag_stable_sort (m01ctc) 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:     aconst Nag_Pointer Input
On entry: the first data field.
2:     bconst Nag_Pointer Input
On entry: the second data field.
6:     orderNag_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:     failNagError *Input/Output
The NAG error argument (see Section 3.6 in the Essential Introduction).

## 6  Error 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, ${\mathbf{n}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{n}}\le 〈\mathit{\text{value}}〉$.
On entry, ${\mathbf{size}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{size}}\le 〈\mathit{\text{value}}〉$.
On entry, ${\mathbf{stride}}=〈\mathit{\text{value}}〉$.
Constraint: $\left|{\mathbf{stride}}\right|\le 〈\mathit{\text{value}}〉$.
These arguments are limited to an implementation-dependent size which 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$.
The absolute value of stride must not be less than size.

## 7  Accuracy

Not applicable.

The time taken by nag_stable_sort (m01ctc) is approximately proportional to $n\mathrm{log}n$.

## 9  Example

The example program reads a three column matrix of real numbers and sorts the first column into ascending order.

### 9.1  Program Text

Program Text (m01ctce.c)

### 9.2  Program Data

Program Data (m01ctce.d)

### 9.3  Program Results

Program Results (m01ctce.r)