A Fast and stable sort routine suitable for efficient, multiple-pass sorting on variable length characters, integers, or real numbers. More...

Functions/Subroutines
subroutine	ordec4 (in, isort, idata, index, n, m, i1, i2)

subroutine	ordec8 (in, isort, idata, index, n, m, i1, i2)

subroutine	order4 (in, isort, idata, index, n, m, i1, i2)

subroutine	orders (in, isort, idata, index, n, m, i1, i2)
	Orders is a fast and stable sort routine suitable for efficient, multiple-pass sorting on variable length characters, integers, or real numbers.

Detailed Description

A Fast and stable sort routine suitable for efficient, multiple-pass sorting on variable length characters, integers, or real numbers.

Author: Jack Woollen

Date: 1999-06-03

Definition in file orders.f.

Function/Subroutine Documentation

◆ ordec4()

subroutine ordec4	(		in,
		dimension(n)	isort,
		character(4), dimension(m,n)	idata,
		dimension(n)	index,
			n,
			m,
			i1,
			i2
	)

Definition at line 331 of file orders.f.

◆ ordec8()

subroutine ordec8	(		in,
		dimension(n)	isort,
		character(8), dimension(m,n)	idata,
		dimension(n)	index,
			n,
			m,
			i1,
			i2
	)

Definition at line 275 of file orders.f.

◆ order4()

subroutine order4	(		in,
		dimension(n)	isort,
		integer(4), dimension(m,n)	idata,
		dimension(n)	index,
			n,
			m,
			i1,
			i2
	)

Definition at line 188 of file orders.f.

◆ orders()

subroutine orders	(		in,
		dimension(n)	isort,
		integer(8), dimension(m,n)	idata,
		dimension(n)	index,
			n,
			m,
			i1,
			i2
	)

Orders is a fast and stable sort routine suitable for efficient, multiple-pass sorting on variable length characters, integers, or real numbers.

The algorithm derives from the radix or bucket sort procedure. The form of the orders subroutine is defined by a cray man page. The sort works by computing frequency distribution of the set of sort keys and using that as a map of the reordered data. Orders rearranges indexes instead of the sort keys, which simplifies multi-pass record sorting. The radix of the sort determines how many "buckets" there are in the frequency distribution array. The larger the radix the more buckets. The simplest is a one bit radix, which has two buckets, and requires as many passes through the keys as the keys have bits. A one byte radix requires less passes through the data with more buckets (256 to be exact). The one byte radix is implemented here. An additional complication is the fact that radix sort only works on key sets of positive values, so this implementation includes a biasing of the (numeric) keys before sorting. To save space the keys themselves are adjusted and then readjusted before returning. A simple example of a one bit radix sort on a list of four, four bit, numbers is diagramed below to illustrate the concept.

-----------------------------------------------------------------------
                 PASS1  >  PASS2  >  PASS3  >  PASS4  >   FINISHED
-----------------------------------------------------------------------
                     |        |        |        |
    THE LIST      0011      0100      0100      1001      0011
                  0101      0011      0101      0011      0100
                  1001      0101      1001      0100      0101
                  0100      1001      0011      0101      1001
-----------------------------------------------------------------------
    BUCKET 0      0100      0100      1001      0011
                     |      0101      0011      0100
                     |      1001       |        0101
-----------------------------------------------------------------------
    BUCKET 1      0011      0011      0100      1001
                  0101        |       0101      |
                  1001        |        |        |
-----------------------------------------------------------------------

PROGRAM HISTORY LOG:

Jack Woollen 1998-02-21 Original version for implementation
Boi Vuong 1998-04-11 Replaced operand .and. with intrinsic iand
D. Keyser 1999-06-03 Modified to port to ibm sp and run in 4 or 8 Byte storage
Jack Woollen 1999-06-09 Added potential for four or eight byte keys in either a four or eight byte environment
Jack Woollen 2012-09-16 Made sorting characters work on little endian

INPUT ARGUMENTS:

Parameters

[in]	IN	Indicator of key form and index state. IN = 0 Initialize indexes and sort characters. IN = 1 Initialize indexes and sort integers. IN = 2 Initialize indexes and sort real numbers. IN = 10 Sort characters with indexes as is. IN = 11 Sort integers with indexes as is. IN = 12 Sort real numbers with indexes asis.
[in]	ISORT	Work array with the same dimension as idata.
[in]	IDATA	Array of sort keys as described by in.
[out]	INDEX	Array of indexes representing the sorted idata.
[in]	N	Dimension of isort, idata, and index.
[in]	M	Offset (in key-words) between successive members of idata.
[in]	I1	Byte length of the key-words.
[in]	I2	Not used; Included for compatability with original cray routine.

Note: The one byte radix method was selected for orders because it offers a good ratio of memory requirement to operation count for producing a sort. Because of recursive manipulation of indexes in one of the loops, this may actually take slightly longer on some vector machines than a (more work intensive) one bit radix method. In general, though, the one byte method is faster. Any larger radix presents exponentially increasing memory required. Note that the implementation uses very little local data space, and only modest user-supplied memory.

Author: Jack Woollen

Date: 1999-06-03