NAG FL Interface
M01 (Sort)
Sorting and Searching

1 Scope of the Chapter

This chapter is concerned with sorting and searching numeric or character data. It handles only the simplest types of data structure and it is concerned only with internal sorting and searching – that is, sorting and searching a set of data which can all be stored within the program.
If you have large files of data or complicated data structures to be sorted or searched you should use a comprehensive sorting or searching program or package.

2 Background to the Problems

2.1 Sorting

The usefulness of sorting is obvious (perhaps a little too obvious, since sorting can be expensive and is sometimes done when not strictly necessary). Sorting may traditionally be associated with data processing and non-numerical programming, but it has many uses within the realm of numerical analysis. For example, within the NAG Library, sorting is used to arrange eigenvalues in ascending order of absolute value, in the manipulation of sparse matrices, and in the ranking of observations for nonparametric statistics.
The general problem may be defined as follows. We are given N items of data
R1,R2,,RN.  
Each item Ri contains a key Ki which can be ordered relative to any other key according to some specified criterion (for example, ascending numeric value). The problem is to determine a permutation
p1,p2,,pN  
which puts the keys in order:
Kp1Kp2KpN.  
Sometimes we may wish actually to rearrange the items so that their keys are in order; for other purposes we may simply require a table of indices so that the items can be referred to in sorted order; or yet again we may require a table of ranks, that is, the positions of each item in the sorted order.
For example, given the single-character items, to be sorted into alphabetic order the indices of the items in sorted order are and the ranks of the items are
Indices may be converted to ranks, and vice versa, by simply computing the inverse permutation.
The items may consist solely of the key (each item may simply be a number). On the other hand, the items may contain additional information (for example, each item may be an eigenvalue of a matrix and its associated eigenvector, the eigenvalue being the key). In the latter case there may be many distinct items with equal keys, and it may be important to preserve the original order among them (if this is achieved, the sorting is called ‘stable’).
There are a number of ingenious algorithms for sorting. For a fascinating discussion of them, and of the whole subject, see Knuth (1973).

2.2 Searching

Searching is a process of retrieving data stored in a computer's memory.
The general problem may be defined as follows:
There are a number of different search algorithms. For more on the subject, see Knuth (1973), Wirth (2004) and Cannizzo (2018).

3 Recommendations on Choice and Use of Available Routines

The following categories of routines are provided:
In the first two and the fourth categories routines are provided for real and integer numeric data, and for character data. In the third category there are routines for rearranging real, complex, integer and character data. Utilities for the manipulation of sparse matrices can be found in Chapter F11.
If the task is simply to rearrange a one-dimensional array of data into sorted order, then an M01C routine should be used, since this requires no extra workspace and is faster than any other method. There are no M01C routines for more complicated data structures, because the cost of rearranging the data is likely to outstrip the cost of comparisons. Instead, a combination of M01D and M01E routines, or some other approach, must be used as described below.
For many applications it is in fact preferable to separate the task of determining the sorted order (ranking) from the task of rearranging data into a pre-determined order; the latter task may not need to be performed at all. Frequently it may be sufficient to refer to the data in sorted order via an index vector, without rearranging it. Frequently also one set of data (e.g., a column of a matrix) is used for determining a set of ranks, which are then applied to other data (e.g., the remaining columns of the matrix).
To determine the ranks of a set of data, use an M01D routine. Routines are provided for ranking one-dimensional arrays, and for ranking rows or columns of two-dimensional arrays. For ranking an arbitrary data structure, use m01dzf, which is, however, much less efficient than the other M01D routines.
To create an index vector so that data can be referred to in sorted order, first call an M01D routine to determine the ranks, and then call m01zaf to convert the vector of ranks into an index vector.
To rearrange data according to pre-determined ranks: use an M01E routine if the data is stored in a one-dimensional array; or if the data is stored in a more complicated structure
To search for an item in a one-dimensional sorted array of data, use an M01N routine. To search for multiple real numbers in a single call, use m01ndf. These M01N routines return the index of the first item with the key equal to the sought-after item or if it is not found, the index of the last item containing the biggest value less than the sought-after item.
Examples of these operations can be found in the routine documents of the relevant routines.

4 Functionality Index

Ranking,  
arbitrary data   m01dzf
columns of a matrix,  
integer numbers   m01dkf
real numbers   m01djf
rows of a matrix,  
integer numbers   m01dff
real numbers   m01def
vector,  
character data   m01dcf
integer numbers   m01dbf
real numbers   m01daf
Rearranging (according to pre-determined ranks):  
vector,  
character data   m01ecf
complex numbers   m01edf
integer numbers   m01ebf
real numbers   m01eaf
Searching (i.e., exact match or the nearest lower value):  
binary search,  
vector,  
integer numbers   m01nbf
real numbers   m01naf
strings   m01ncf
direct search,  
vector,  
real numbers   m01ndf
Service routines,  
check validity of a permutation   m01zbf
decompose a permutation into cycles   m01zcf
invert a permutation (ranks to indices or vice versa)   m01zaf
Sorting (i.e., rearranging into sorted order):  
quick sort,  
vector,  
character data   m01ccf
integer numbers   m01cbf
real numbers   m01caf

5 Auxiliary Routines Associated with Library Routine Arguments

None.

6 Withdrawn or Deprecated Routines

None.

7 References

Cannizzo F (2018) A fast and vectorizable alternative to binary search in O(1) with wide applicability to arrays of floating point numbers Journal of Parallel and Distributed Computing 113 37–54
Knuth D E (1973) The Art of Computer Programming (Volume 3) (2nd Edition) Addison–Wesley
Wirth N (2004) Algorithms and Data Structures 35–36 Prentice Hall