ISORTS, SSORTS, and DSORTS (Sort the Elements of a Sequence Using a Stable Sort and Note the Original Element Positions)

Purpose

These subroutines sort the elements of sequence x using a stable sort; that is, where equal elements occur in the input sequence, they remain in the same relative order in the output sequence. The original positions of the elements in sequence x are returned in the indices array INDX.

Note: If you need a stable sort, then you should use these subroutines rather than ISORTX, SSORTX, or DSORTX.

Table 1. Data Types
Data Types
x, `work`	Subroutine
Integer	ISORTS
Short-precision real	SSORTS
Long-precision real	DSORTS

Syntax

Language	Syntax
Fortran	CALL ISORTS \| SSORTS \| DSORTS (`x`, `incx`, `n`, `indx`, `work`, `lwork`)
C and C++	isorts \| ssorts \| dsorts (`x`, `incx`, `n`, `indx`, `work`, `lwork`);

On Entry
x: is the sequence x of length n, to be sorted.
Specified as: a one-dimensional array of (at least) length 1+(n-1)|incx| elements, containing numbers of the data type indicated in Table 1.
incx: is the stride for both the input sequence x and the output sequence x. If it is positive, elements are sorted into ascending order in the array, and if it is negative, elements are sorted into descending order in the array.
Specified as: an integer. It can have any value.
n: is the number of elements in sequence x. Specified as: an integer; n ≥ 0.
indx: See On Return.
work: is the storage work area used by this subroutine. Its size is specified by lwork.
Specified as: an area of storage, containing numbers of the data type indicated in Table 1.
lwork: is the size of the work area specified by work— that is, the number of elements in work.
Specified as: an integer; lwork ≥ n/2.

Note: This is the value to achieve optimal performance. The sort is performed regardless of the value you specify for lwork, but you may receive an attention message.

On Return
x: is the sequence x of length n, with its elements sorted into designated order in the array. Returned as: a one-dimensional array, containing numbers of the data type indicated in Table 1.
indx: is the array, referred to as INDX, containing the n indices that indicate, for the elements in the sorted output sequence, the original positions of those elements in input sequence x.
Note: It is important to remember that when you specify a negative stride, ESSL assumes that the order of the input and output sequence elements in the X array is reversed; however, the elements in INDX are not reversed. See Function.

Returned as: a one-dimensional array of length n, containing integers; 1 ≤ (INDX elements) ≤ n.

Function

The elements of input sequence x are sorted into ascending order using a partition sort. The sorting is stable; that is, where equal elements occur in the input sequence, they remain in the same relative order in the output sequence. The elements of output sequence x can be expressed as follows:

x₁ ≤ x₂ ≤ x₃ ≤ … ≤ x_n

By specifying a negative stride for x, the elements of input sequence x are assumed to be reversed in the array, (x_n, x_n-1, … , x₁), thus producing a sort into descending order within the array.

In addition, the INDX array contains the n indices that indicate, for the elements in the sorted output sequence, the original positions of those elements in input sequence x. (These are not the positions in the array, but rather the positions in the sequence.) For each element x_j in the input sequence, becoming element xx_k in the output sequence, the elements in INDX are defined as follows:

INDX(k) = j for j = 1, n and k = 1, n
where xx_k = x_j

To understand INDX when you specify a negative stride, you should remember that both the input and output sequences, x, are assumed to be in reverse order in array X, but INDX is not affected by stride. The sequence elements of x are assumed to be stored in your input array as follows:

X = (x_n, x_n-1, … , x₁)

The sequence elements of x are stored in your output array by ESSL as follows:

X = (xx_n, xx_n-1, … , xx₁)

where the elements xx_k are the elements x_j, sorted into descending order in X. As an example of how INDX is calculated, if xx₁ = x_n-1, then INDX(1) = n-1.

If n is 0, no computation is performed. See references [38] and [91].

Error conditions

Resource Errors: Unable to allocate internal work area.
Computational Errors: None
Input-Argument Errors: n < 0

Examples

Example 1

This example shows how to sort a sequence x into ascending order by specifying a positive stride. Because this is a stable sort, the -1 elements remain in the same relative order in the output sequence, indicated by INDX(2) = 2 and INDX(3) = 4.

Call Statement and Input:

             X  INCX  N   INDX   WORK  LWORK
             |   |    |    |      |      |
CALL ISORTS( X , 2  , 5 , INDX , WORK ,  5  )
 
X        =  (2, . , -1, . , 5, . , -1, . , -2)

Output:

X        =  (-2, . , -1, . , -1, . , 2, . , 5)
INDX     =  (5, 2, 4, 1, 3)

Example 2

This example shows how to sort a sequence x into descending order by specifying a negative stride. Therefore, both the input and output sequences are assumed to be reversed in the array X. The input sequence is assumed to be stored as follows:

X = (x₅, x₄, x₃, x₂, x₁) = (2, -1, 5, -1, -2)

The output sequence is stored by ESSL as follows:

X = (xx₅, xx₄, xx₃, xx₂, xx₁) = (5, 2, -1, -1, -2)

As a result, INDX is defined as follows:

INDX = (indx₁, indx₂, indx₃, indx₄, indx₅) = (1, 2, 4, 5, 3)

For example, because output sequence element xx₄ = 2 is input sequence element x₅, then INDX(4) = 5. Also, because this is a stable sort, the -1 elements remain in the same relative order in the output sequence, indicated by INDX(2) = 2 and INDX(3) = 4.

Call Statement and Input:

             X   INCX  N   INDX   WORK  LWORK
             |    |    |    |      |      |
CALL ISORTS( X , -1  , 5 , INDX , WORK ,  5  )
 
X        =  (2, -1, 5, -1, -2)

Output:

X        =  (5, 2, -1, -1, -2)
INDX     =  (1, 2, 4, 5, 3)