This module implements overloaded sorting subroutines named ORD_SORT,
SORT_INDEX, and SORT, that each can be used to sort two kinds
of INTEGER arrays, two kinds of REAL arrays, character(len=*) arrays
By default sorting is in order of
increasing value, but there is an option to sort in decreasing order.
All the subroutines have worst case run time performance of O(N Ln(N)),
but on largely sorted data ORD_SORT and SORT_INDEX can have a run time
performance of O(N).
ORD_SORT is a translation of the "Rust" sort sorting algorithm in
slice.rs:
https://github.com/rust-lang/rust/blob/90eb44a5897c39e3dff9c7e48e3973671dcd9496/src/liballoc/slice.rs
which in turn is inspired by the timsort algorithm of Tim Peters,
http://svn.python.org/projects/python/trunk/Objects/listsort.txt.
ORD_SORT is a hybrid stable comparison algorithm combining merge sort,
and insertion sort. It is always at worst O(N Ln(N)) in sorting random
data, having a performance about 25% slower than SORT on such
data, but has much better performance than SORT on partially
sorted data, having O(N) performance on uniformly non-increasing or
non-decreasing data.
SORT_INDEX is a modification of ORD_SORT so that in addition to
sorting the input array, it returns the indices that map to a
stable sort of the original array. These indices are
intended to be used to sort data that is correlated with the input
array, e.g., different arrays in a database, different columns of a
rank 2 array, different elements of a derived type. It is less
efficient than ORD_SORT at sorting a simple array.
SORT uses the INTROSORT sorting algorithm of David Musser,
http://www.cs.rpi.edu/~musser/gp/introsort.ps. introsort is a hybrid
unstable comparison algorithm combining quicksort, insertion sort, and
heap sort. While this algorithm is always O(N Ln(N)) it is relatively
fast on randomly ordered data, but inconsistent in performance on partly
sorted data, sometimes having merge sort performance, sometimes having
better than quicksort performance. UNORD_SOORT is about 25%
more efficient than ORD_SORT at sorting purely random data, but af an
order of Ln(N) less efficient at sorting partially sorted data.