NAG CL Interface
m01ctc (stable_​sort)

Settings help

CL Name Style:


1 Purpose

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

2 Specification

#include <nag.h>
void  m01ctc (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)
The function may be called by the names: m01ctc, nag_sort_stable_sort or nag_stable_sort.

3 Description

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 m01dsc, m01zac and m01esc in order to carry out a stable sort with the same specification as m01csc. m01ctc will be faster than 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 m01csc.

4 References

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

5 Arguments

1: vec[n] Pointer  Input/Output
On entry: the array of objects to be sorted.
On exit: the objects rearranged into sorted order.
2: n size_t Input
On entry: the number n of objects to be sorted.
Constraint: 0nMAX_LENGTH, where MAX_LENGTH is an implementation-dependent value for the maximum size of an array.
3: size size_t Input
On entry: the size of each object to be sorted.
Constraint: 1sizep, where p is an implementation-dependent value for the maximum size_t size on the system, divided by n if n is positive.
4: stride ptrdiff_t Input
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: size|stride|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: compare function, supplied by the user External Function
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,
-0 if the first data field is equal to the second,
-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: a const Nag_Pointer  Input
On entry: the first data field.
2: b const Nag_Pointer  Input
On entry: the second data field.
6: order Nag_SortOrder Input
On entry: specifies whether the array is to be sorted into ascending or descending order.
Constraint: order=Nag_Ascending or Nag_Descending.
7: 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_2_INT_ARG_LT
On entry, |stride| = value while size=value . These arguments must satisfy |stride| size .
NE_ALLOC_FAIL
Dynamic memory allocation failed.
NE_BAD_PARAM
On entry, argument order had an illegal value.
NE_INT_ARG_GT
On entry, n=value.
Constraint: nvalue, an implementation-dependent size that is printed in the error message.
On entry, size=value.
Constraint: sizevalue, an implementation-dependent size that is printed in the error message.
On entry, stride=value.
Constraint: |stride|value, an implementation-dependent size that is printed in the error message.
NE_INT_ARG_LT
On entry, n=value.
Constraint: n0.
On entry, size=value.
Constraint: size1.

7 Accuracy

Not applicable.

8 Parallelism and Performance

m01ctc is not threaded in any implementation.

9 Further Comments

The time taken by m01ctc is approximately proportional to n log(n) .

10 Example

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

10.1 Program Text

Program Text (m01ctce.c)

10.2 Program Data

Program Data (m01ctce.d)

10.3 Program Results

Program Results (m01ctce.r)