hide long namesshow long names
hide short namesshow short names
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_realvec_sort (m01ca)


    1  Purpose
    2  Syntax
    7  Accuracy
    9  Example


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


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


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.


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


Compulsory Input Parameters

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

Optional Input Parameters

1:     m2 int64int32nag_int scalar
Default: the dimension of the array rv.
The index of the last element of rv to be sorted.
Constraint: m2m1.

Output Parameters

1:     rvm2 – double array
These values are rearranged into sorted order.
2:     ifail int64int32nag_int scalar
ifail=0 unless the function detects an error (see Error Indicators and Warnings).

Error Indicators and Warnings

Errors or warnings detected by the function:
On entry,m2<1,
On entry,order is not 'A' or 'D'.
An unexpected error has been triggered by this routine. Please contact NAG.
Your licence key may have expired or may not have been installed correctly.
Dynamic memory allocation failed.


Not applicable.

Further Comments

The average time taken by nag_sort_realvec_sort (m01ca) is approximately proportional to n×logn, where n=m2-m1+1. The worst case time is proportional to n2 but this is extremely unlikely to occur.


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');

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

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–2015