This submodule implements the overloaded sorting subroutine SORT
that can be used to sort four kinds of INTEGER
arrays and three kinds
of REAL
arrays. Sorting is in order of increasing value, with the worst
case run time performance of O(N Ln(N))
.
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.