Integer type:  int32  int64  nag_int  show int32  show int32  show int64  show int64  show nag_int  show nag_int

Chapter Contents
Chapter Introduction
NAG Toolbox

# NAG Toolbox: nag_sort_realvec_sort (m01ca)

## Purpose

nag_sort_realvec_sort (m01ca) rearranges a vector of double numbers into ascending or descending order.

## Syntax

[rv, ifail] = m01ca(rv, m1, order, 'm2', m2)
[rv, ifail] = nag_sort_realvec_sort(rv, m1, order, 'm2', m2)

## Description

nag_sort_realvec_sort (m01ca) 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.

## References

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

## Parameters

### Compulsory Input Parameters

1:     $\mathrm{rv}\left({\mathbf{m2}}\right)$ – double array
Elements m1 to m2 of rv must contain double values to be sorted.
2:     $\mathrm{m1}$int64int32nag_int scalar
The index of the first element of rv to be sorted.
Constraint: ${\mathbf{m1}}>0$.
3:     $\mathrm{order}$ – string (length ≥ 1)
If ${\mathbf{order}}=\text{'A'}$, the values will be sorted into ascending (i.e., nondecreasing) order.
If ${\mathbf{order}}=\text{'D'}$, into descending order.
Constraint: ${\mathbf{order}}=\text{'A'}$ or $\text{'D'}$.

### Optional Input Parameters

1:     $\mathrm{m2}$int64int32nag_int scalar
Default: the dimension of the array rv.
The index of the last element of rv to be sorted.
Constraint: ${\mathbf{m2}}\ge {\mathbf{m1}}$.

### Output Parameters

1:     $\mathrm{rv}\left({\mathbf{m2}}\right)$ – double array
These values are rearranged into sorted order.
2:     $\mathrm{ifail}$int64int32nag_int scalar
${\mathbf{ifail}}={\mathbf{0}}$ unless the function detects an error (see Error Indicators and Warnings).

## Error Indicators and Warnings

Errors or warnings detected by the function:
${\mathbf{ifail}}=1$
 On entry, ${\mathbf{m2}}<1$, or ${\mathbf{m1}}<1$, or ${\mathbf{m1}}>{\mathbf{m2}}$.
${\mathbf{ifail}}=2$
 On entry, order is not 'A' or 'D'.
${\mathbf{ifail}}=-99$
${\mathbf{ifail}}=-399$
Your licence key may have expired or may not have been installed correctly.
${\mathbf{ifail}}=-999$
Dynamic memory allocation failed.

## Accuracy

Not applicable.

The average time taken by nag_sort_realvec_sort (m01ca) is approximately proportional to $n×\mathrm{log}\left(n\right)$, where $n={\mathbf{m2}}-{\mathbf{m1}}+1$. The worst case time is proportional to ${n}^{2}$ but this is extremely unlikely to occur.

## Example

This example reads a list of double numbers and sorts them into ascending order.
```function m01ca_example

fprintf('m01ca example results\n\n');

rv = [1.3,     5.9,     4.1,     2.3,     0.5,     5.8,     1.3,     6.5, ...
2.3,     0.5,     6.5,     9.9,     2.1,     1.1,     1.2,     8.6];
m1 = int64(1);
order = 'Ascending';

[rv, ifail] = m01ca(rv, m1, order);

fprintf('Sorted numbers:\n\n');
fprintf('%7.1f%7.1f%7.1f%7.1f%7.1f%7.1f%7.1f%7.1f\n',rv);

```
```m01ca example results

Sorted numbers:

0.5    0.5    1.1    1.2    1.3    1.3    2.1    2.3
2.3    4.1    5.8    5.9    6.5    6.5    8.6    9.9
```