---

Manual Reference Pages  - sort (3m_unicode)

---

NAME

SORT(3f) - [M_unicode:SORT] indexed hybrid quicksort of an array (LICENSE:MIT)

CONTENTS

Synopsis
Description
Background
Examples
Author
License

SYNOPSIS

subroutine sort(data,index)

          type(unicode_type),intent(in) :: data(:)
          integer,intent(out)           :: indx(size(data))

DESCRIPTION

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 would require a significant amount of memory. One major advantage of this method is that the indices can be used to access an entire user-defined type in sorted order. This makes this seemingly simple sort procedure usable with the vast majority of user-defined types. or other correlated data.

BACKGROUND

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(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
o	type(unicode_type) version JSU 2025-09-20. See M_sort for other types.

EXAMPLES

Sample usage:

   program demo_sort
   use iso_fortran_env, only : stdout => output_unit
   use M_unicode,       only : sort, unicode_type, assignment(=)
   use M_unicode,       only : ut=>unicode_type, write(formatted)
   use M_unicode,       only : ch=>character
   implicit none
   character(len=*),parameter :: g=’(*(g0,1x))’
   integer,parameter          :: isz=4
   type(unicode_type)         :: rr(isz)
   integer                    :: ii(isz)
   integer                    :: i
      !
      write(stdout,g)’sort array with sort(3f)’
      rr=[ &
       ut("the"),   &
       ut("quick"), &
       ut("brown"), &
       ut("fox") ]
      !
      write(stdout,g)’original order’
      write(stdout,g)ch(rr)
      !
      call sort(rr,ii)
      !
      write(stdout,g)’sorted order’
      ! convert to character
      do i=1,size(rr)
         write(stdout,’(i3.3,1x,a)’)i,rr(ii(i))%character()
      enddo
      !
      write(stdout,g)’reorder original’
      rr=rr(ii)
      write(stdout,g)ch(rr)
   end program demo_sort

Results:

   > sort array with sort(3f)
   > original order
   > the quick brown fox
   > sorted order
   > 001 brown
   > 002 fox
   > 003 quick
   > 004 the
   > reorder original
   > brown fox quick the

AUTHOR

John S. Urban

LICENSE

    MIT

---