sort_quick_rx Interface

sort_quick_rx(3f) - [M_sort:sort:quicksort] indexed hybrid quicksort of an array
(LICENSE:PD)

  subroutine sort_quick_rx(data,index)

   ! one of
      real,intent(in)            :: data(:)
      doubleprecision,intent(in) :: data(:)
      integer,intent(in)         :: data(:)
      character,intent(in)       :: data(:)
      complex,intent(in)         :: data(:)

   integer,intent(out)           :: indx(size(data))

A rank hybrid quicksort. The data is not moved. An integer array is
generated instead with values that are indices to the sorted order
of the data. This requires a second array the size of the input
array, which for large arrays could require a significant amount of
memory. One major advantage of this method is that any element of a
user-defined type that is a scalar intrinsic can be used to provide the
sort data and subsequently the indices can be used to access the entire
user-defined type in sorted order. This makes this seemingly simple
sort procedure usuable with the vast majority of user-defined types.

From Leonard J. Moss of SLAC:

Here's a hybrid QuickSort I wrote a number of years ago. It's
based on suggestions in Knuth, Volume 3, and performs much better
than a pure QuickSort on short or partially ordered input arrays.

This routine performs an in-memory sort of the first N elements of
array DATA, returning into array INDEX the indices of elements of
DATA arranged in ascending order. Thus,

   DATA(INDX(1)) will be the smallest number in array DATA;
   DATA(INDX(N)) will be the largest number in DATA.

The original data is not physically rearranged. The original order
of equal input values is not necessarily preserved.

sort_quick_rx(3f) uses a hybrid QuickSort algorithm, based on several
suggestions in Knuth, Volume 3, Section 5.2.2. In particular, the
"pivot key" [my term] for dividing each subsequence is chosen to be
the median of the first, last, and middle values of the subsequence;
and the QuickSort is cut off when a subsequence has 9 or fewer
elements, and a straight insertion sort of the entire array is done
at the end. The result is comparable to a pure insertion sort for
very short arrays, and very fast for very large arrays (of order 12
micro-sec/element on the 3081K for arrays of 10K elements). It is
also not subject to the poor performance of the pure QuickSort on
partially ordered data.

Complex values are sorted by the magnitude of sqrt(r**2+i**2).

o Created: sortrx(3f): 15 Jul 1986, Len Moss
o saved from url=(0044)http://www.fortran.com/fortran/quick_sort2.f
o changed to update syntax from F77 style; John S. Urban 20161021
o generalized from only real values to include other intrinsic types;
  John S. Urban 20210110

program demo_sort_quick_rx
use M_sort, only : sort_quick_rx
implicit none
integer,parameter            :: isz=10000
real                         :: rr(isz)
integer                      :: ii(isz)
integer                      :: i
write(*,*)'initializing array with ',isz,' random numbers'
CALL RANDOM_NUMBER(RR)
rr=rr*450000.0
write(*,*)'sort real array with sort_quick_rx(3f)'
call sort_quick_rx(rr,ii)
write(*,*)'checking index of sort_quick_rx(3f)'
do i=1,isz-1
   if(rr(ii(i)).gt.rr(ii(i+1)))then
      write(*,*)'Error in sorting reals small to large ', &
      & i,rr(ii(i)),rr(ii(i+1))
   endif
enddo
write(*,*)'test of sort_quick_rx(3f) complete'
! use the index array to actually move the input array into a sorted
! order
rr=rr(ii)
do i=1,isz-1
   if(rr(i).gt.rr(i+1))then
      write(*,*)'Error in sorting reals small to large ', &
      & i,rr(i),rr(i+1)
   endif
enddo
write(*,*)'test of sort_quick_rx(3f) complete'
end program demo_sort_quick_rx

 initializing array with        10000  random numbers
 sort real array with sort_quick_rx(3f)
 checking index of sort_quick_rx(3f)
 test of sort_quick_rx(3f) complete
 test of sort_quick_rx(3f) complete