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_intvec_sort (m01cb)


    1  Purpose
    2  Syntax
    7  Accuracy
    9  Example


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


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


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.


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:     ivm2 int64int32nag_int array
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.
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 iv.
The index of the last element of iv to be sorted.
Constraint: m2m1.

Output Parameters

1:     ivm2 int64int32nag_int 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 the function 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 integers and sorts them into descending order.
function m01cb_example

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

iv = [int64(23) 45 45 67 69 90 999 1 78 112 24 69 96 99 45 78];
m1 = int64(1);
order = 'Descending';

[iv, ifail] = m01cb(iv, m1, order);

fprintf('Sorted numbers:\n\n');

m01cb example results

Sorted numbers:

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

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