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

PDF version (NAG web site, 64-bit version, 64-bit version)
Chapter Contents
Chapter Introduction
NAG Toolbox

# NAG Toolbox: nag_sort_intvec_sort (m01cb)

## Purpose

nag_sort_intvec_sort (m01cb) rearranges a vector of integer numbers into ascending or descending order.

## Syntax

[iv, ifail] = m01cb(iv, m1, order, 'm2', m2)
[iv, ifail] = nag_sort_intvec_sort(iv, m1, order, 'm2', m2)

## Description

nag_sort_intvec_sort (m01cb) 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:     iv(m2) – int64int32nag_int array
m2, the dimension of the array, must satisfy the constraint m2m1${\mathbf{m2}}\ge {\mathbf{m1}}$.
Elements m1 to m2 of iv must contain integer values to be sorted.
2:     m1 – int64int32nag_int scalar
The index of the first element of iv to be sorted.
Constraint: m1 > 0${\mathbf{m1}}>0$.
3:     order – string (length ≥ 1)
If order = 'A'${\mathbf{order}}=\text{'A'}$, the values will be sorted into ascending (i.e., nondecreasing) order.
If order = 'D'${\mathbf{order}}=\text{'D'}$, into descending order.
Constraint: order = 'A'${\mathbf{order}}=\text{'A'}$ or 'D'$\text{'D'}$.

### Optional Input Parameters

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

None.

### Output Parameters

1:     iv(m2) – int64int32nag_int array
These values are rearranged into sorted order.
2:     ifail – int64int32nag_int scalar
${\mathrm{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:
ifail = 1${\mathbf{ifail}}=1$
 On entry, m2 < 1${\mathbf{m2}}<1$, or m1 < 1${\mathbf{m1}}<1$, or m1 > m2${\mathbf{m1}}>{\mathbf{m2}}$.
ifail = 2${\mathbf{ifail}}=2$
 On entry, order is not 'A' or 'D'.

## Accuracy

Not applicable.

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

## Example

```function nag_sort_intvec_sort_example
iv = [int64(23);45;45;67;69;90;999;1;78;112;24;69;96;99;45;78];
m1 = int64(1);
order = 'Descending';
[ivOut, ifail] = nag_sort_intvec_sort(iv, m1, order)
```
```

ivOut =

999
112
99
96
90
78
78
69
69
67
45
45
45
24
23
1

ifail =

0

```
```function m01cb_example
iv = [int64(23);45;45;67;69;90;999;1;78;112;24;69;96;99;45;78];
m1 = int64(1);
order = 'Descending';
[ivOut, ifail] = m01cb(iv, m1, order)
```
```

ivOut =

999
112
99
96
90
78
78
69
69
67
45
45
45
24
23
1

ifail =

0

```

PDF version (NAG web site, 64-bit version, 64-bit version)
Chapter Contents
Chapter Introduction
NAG Toolbox

© The Numerical Algorithms Group Ltd, Oxford, UK. 2009–2013