pic_sorting Module

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.

Reporting failures through error_t

ORD_SORT, SORT_INDEX and RADIX_SORT accept an optional err argument of type error_t from pic_error:

    use pic_error, only: error_t
    type(error_t) :: err
    call ord_sort( array, work, err=err )
    if (err%has_error()) call err%print_trace()

When err is present a detected failure sets it and the routine returns early without completing the sort. When err is absent the routine keeps its historical behaviour and aborts the process with error stop: these routines are (or contain) pure code, and a pure procedure can neither perform output nor error stop with a run-time message, so there is no way to report a failure other than through err.

The codes used are

  • ERROR_VALIDATION - a caller supplied work or iwork scratch array is too small for array;
  • ERROR_BOUNDS - index is too small for array, or array has more elements than the kind of index can number;
  • ERROR_ALLOC - an internal scratch buffer could not be allocated;
  • ERROR_INTERNAL - an internal invariant of the merge sort was violated. That is a bug in PIC, not bad input.

State of the arguments when err has been set:

  • For ERROR_VALIDATION, ERROR_BOUNDS and ERROR_ALLOC the failure is detected before any merging begins, so array still holds its input values - except that SORT_INDEX called with reverse = .true. has already reversed array in place and leaves it reversed.
  • ERROR_INTERNAL is raised after merging, so array is then an unspecified permutation of its input.
  • index, work and iwork are intent(out), so they are undefined whenever err is set. SORT_INDEX happens to leave index holding the identity permutation on a work/iwork/allocation failure, but callers must not rely on that.

SORT takes no err argument: it allocates nothing and validates nothing, so it has no failure to report.

The generic subroutine implementing the SORT algorithm to return an input array with its elements sorted in order of (non-)decreasing value. Its use has the syntax:

 call sort( array[, reverse] )

with the arguments:

  • array: the rank 1 array to be sorted. It is an intent(inout) argument of any of the types integer(int8), integer(int16), integer(int32), integer(int64), real(real32), real(real64), real(real128), character(*), type(string_type), type(bitset_64), type(bitset_large). If both the type of array is real and at least one of the elements is a NaN, then the ordering of the result is undefined. Otherwise it is defined to be the original elements in non-decreasing order.
  • reverse (optional): shall be a scalar of type default logical. It is an intent(in) argument. If present with a value of .true. then array will be sorted in order of non-increasing values in unstable order. Otherwise index will sort array in order of non-decreasing values in unstable order.

Example

    ...
    ! Read random data from a file
    call read_file( 'dummy_file', array )
    ! Sort the random data
    call sort( array )
    ! Process the sorted data
    call array_search( array, values )
    ...

Uses

  • module~~pic_sorting~~UsesGraph module~pic_sorting pic_sorting module~pic_error pic_error module~pic_sorting->module~pic_error module~pic_optional_value pic_optional_value module~pic_sorting->module~pic_optional_value module~pic_types pic_types module~pic_sorting->module~pic_types module~pic_error->module~pic_types module~pic_global_definitions pic_global_definitions module~pic_error->module~pic_global_definitions module~pic_optional_value->module~pic_types iso_c_binding iso_c_binding module~pic_types->iso_c_binding iso_fortran_env iso_fortran_env module~pic_types->iso_fortran_env module~pic_global_definitions->module~pic_types

Used by

  • module~~pic_sorting~~UsedByGraph module~pic_sorting pic_sorting module~pic_profiler pic_profiler module~pic_profiler->module~pic_sorting module~pic_sorting_ord_sort pic_sorting_ord_sort module~pic_sorting_ord_sort->module~pic_sorting module~pic_sorting_radix_sort pic_sorting_radix_sort module~pic_sorting_radix_sort->module~pic_sorting module~pic_sorting_sort pic_sorting_sort module~pic_sorting_sort->module~pic_sorting module~pic_sorting_sort_index pic_sorting_sort_index module~pic_sorting_sort_index->module~pic_sorting

Interfaces

public interface ord_sort

The generic subroutine interface implementing the ORD_SORT algorithm, a translation to Fortran 2008, of the "Rust" sort algorithm found in slice.rs https://github.com/rust-lang/rust/blob/90eb44a5897c39e3dff9c7e48e3973671dcd9496/src/liballoc/slice.rs#L2159 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.

  • private module subroutine char_ord_sort(array, work, reverse, err)

    char_ord_sort( array ) sorts the input ARRAY of type character(len=*) using a hybrid sort based on the "Rust" sort algorithm found in slice.rs

    Arguments

    Type IntentOptional Attributes Name
    character(len=*), intent(inout) :: array(0:)
    character(len=len), intent(out), optional :: work(0:)
    logical, intent(in), optional :: reverse
    type(error_t), intent(inout), optional :: err

  • private module subroutine dp_ord_sort(array, work, reverse, err)

    dp_ord_sort( array ) sorts the input ARRAY of type real(dp) using a hybrid sort based on the "Rust" sort algorithm found in slice.rs

    Arguments

    Type IntentOptional Attributes Name
    real(kind=dp), intent(inout) :: array(0:)
    real(kind=dp), intent(out), optional :: work(0:)
    logical, intent(in), optional :: reverse
    type(error_t), intent(inout), optional :: err

  • private module subroutine int32_ord_sort(array, work, reverse, err)

    int32_ord_sort( array ) sorts the input ARRAY of type integer(int32) using a hybrid sort based on the "Rust" sort algorithm found in slice.rs

    Arguments

    Type IntentOptional Attributes Name
    integer(kind=int32), intent(inout) :: array(0:)
    integer(kind=int32), intent(out), optional :: work(0:)
    logical, intent(in), optional :: reverse
    type(error_t), intent(inout), optional :: err

  • private module subroutine int64_ord_sort(array, work, reverse, err)

    int64_ord_sort( array ) sorts the input ARRAY of type integer(int64) using a hybrid sort based on the "Rust" sort algorithm found in slice.rs

    Arguments

    Type IntentOptional Attributes Name
    integer(kind=int64), intent(inout) :: array(0:)
    integer(kind=int64), intent(out), optional :: work(0:)
    logical, intent(in), optional :: reverse
    type(error_t), intent(inout), optional :: err

  • private module subroutine sp_ord_sort(array, work, reverse, err)

    sp_ord_sort( array ) sorts the input ARRAY of type real(sp) using a hybrid sort based on the "Rust" sort algorithm found in slice.rs

    Arguments

    Type IntentOptional Attributes Name
    real(kind=sp), intent(inout) :: array(0:)
    real(kind=sp), intent(out), optional :: work(0:)
    logical, intent(in), optional :: reverse
    type(error_t), intent(inout), optional :: err

public interface radix_sort

The generic subroutine interface implementing the LSD radix sort algorithm, see https://en.wikipedia.org/wiki/Radix_sort for more details. It is always O(N) in sorting random data, but need a O(N) buffer. (Specification)

  • private module subroutine dp_radix_sort(array, work, reverse, err)

    Arguments

    Type IntentOptional Attributes Name
    real(kind=dp), intent(inout), dimension(:), target :: array
    real(kind=dp), intent(inout), optional, dimension(:), target :: work
    logical, intent(in), optional :: reverse
    type(error_t), intent(inout), optional :: err

  • private pure module subroutine int32_radix_sort(array, work, reverse, err)

    Arguments

    Type IntentOptional Attributes Name
    integer(kind=int32), intent(inout), dimension(:) :: array
    integer(kind=int32), intent(inout), optional, dimension(:), target :: work
    logical, intent(in), optional :: reverse
    type(error_t), intent(inout), optional :: err

  • private pure module subroutine int64_radix_sort(array, work, reverse, err)

    Arguments

    Type IntentOptional Attributes Name
    integer(kind=int64), intent(inout), dimension(:) :: array
    integer(kind=int64), intent(inout), optional, dimension(:), target :: work
    logical, intent(in), optional :: reverse
    type(error_t), intent(inout), optional :: err

  • private module subroutine sp_radix_sort(array, work, reverse, err)

    Arguments

    Type IntentOptional Attributes Name
    real(kind=sp), intent(inout), dimension(:), target :: array
    real(kind=sp), intent(inout), optional, dimension(:), target :: work
    logical, intent(in), optional :: reverse
    type(error_t), intent(inout), optional :: err

public interface sort

The generic subroutine interface implementing the SORT algorithm, based on the introsort of David Musser. (Specification)

  • private pure module subroutine char_sort(array, reverse)

    char_sort( array[, reverse] ) sorts the input ARRAY of type character(len=*) using a hybrid sort based on the introsort of David Musser. The algorithm is of order O(N Ln(N)) for all inputs. Because it relies on quicksort, the coefficient of the O(N Ln(N)) behavior is small for random data compared to other sorting algorithms.

    Arguments

    Type IntentOptional Attributes Name
    character(len=*), intent(inout) :: array(0:)
    logical, intent(in), optional :: reverse

  • private pure module subroutine dp_sort(array, reverse)

    dp_sort( array[, reverse] ) sorts the input ARRAY of type real(dp) using a hybrid sort based on the introsort of David Musser. The algorithm is of order O(N Ln(N)) for all inputs. Because it relies on quicksort, the coefficient of the O(N Ln(N)) behavior is small for random data compared to other sorting algorithms.

    Arguments

    Type IntentOptional Attributes Name
    real(kind=dp), intent(inout) :: array(0:)
    logical, intent(in), optional :: reverse

  • private pure module subroutine int32_sort(array, reverse)

    int32_sort( array[, reverse] ) sorts the input ARRAY of type integer(int32) using a hybrid sort based on the introsort of David Musser. The algorithm is of order O(N Ln(N)) for all inputs. Because it relies on quicksort, the coefficient of the O(N Ln(N)) behavior is small for random data compared to other sorting algorithms.

    Arguments

    Type IntentOptional Attributes Name
    integer(kind=int32), intent(inout) :: array(0:)
    logical, intent(in), optional :: reverse

  • private pure module subroutine int64_sort(array, reverse)

    int64_sort( array[, reverse] ) sorts the input ARRAY of type integer(int64) using a hybrid sort based on the introsort of David Musser. The algorithm is of order O(N Ln(N)) for all inputs. Because it relies on quicksort, the coefficient of the O(N Ln(N)) behavior is small for random data compared to other sorting algorithms.

    Arguments

    Type IntentOptional Attributes Name
    integer(kind=int64), intent(inout) :: array(0:)
    logical, intent(in), optional :: reverse

  • private pure module subroutine sp_sort(array, reverse)

    sp_sort( array[, reverse] ) sorts the input ARRAY of type real(sp) using a hybrid sort based on the introsort of David Musser. The algorithm is of order O(N Ln(N)) for all inputs. Because it relies on quicksort, the coefficient of the O(N Ln(N)) behavior is small for random data compared to other sorting algorithms.

    Arguments

    Type IntentOptional Attributes Name
    real(kind=sp), intent(inout) :: array(0:)
    logical, intent(in), optional :: reverse

public interface sort_index

The generic subroutine interface implementing the SORT_INDEX algorithm, based on the "Rust" sort algorithm found in slice.rs https://github.com/rust-lang/rust/blob/90eb44a5897c39e3dff9c7e48e3973671dcd9496/src/liballoc/slice.rs#L2159 but modified to return an array of indices that would provide a stable sort of the rank one ARRAY input.

The indices by default correspond to a non-decreasing sort, but if the optional argument REVERSE is present with a value of .TRUE. the indices correspond to a non-increasing sort.

  • private module subroutine char_sort_index_default(array, index, work, iwork, reverse, err)

    char_sort_index_default( array, index[, work, iwork, reverse] ) sorts an input ARRAY of type character(len=*) using a hybrid sort based on the "Rust" sort algorithm found in slice.rs and returns the sorted ARRAY and an array INDEX of indices in the order that would sort the input ARRAY in the desired direction.

    Arguments

    Type IntentOptional Attributes Name
    character(len=*), intent(inout) :: array(0:)
    integer(kind=int_index), intent(out) :: index(0:)
    character(len=len), intent(out), optional :: work(0:)
    integer(kind=int_index), intent(out), optional :: iwork(0:)
    logical, intent(in), optional :: reverse
    type(error_t), intent(inout), optional :: err

  • private module subroutine char_sort_index_low(array, index, work, iwork, reverse, err)

    char_sort_index_low( array, index[, work, iwork, reverse] ) sorts an input ARRAY of type character(len=*) using a hybrid sort based on the "Rust" sort algorithm found in slice.rs and returns the sorted ARRAY and an array INDEX of indices in the order that would sort the input ARRAY in the desired direction.

    Arguments

    Type IntentOptional Attributes Name
    character(len=*), intent(inout) :: array(0:)
    integer(kind=int_index_low), intent(out) :: index(0:)
    character(len=len), intent(out), optional :: work(0:)
    integer(kind=int_index_low), intent(out), optional :: iwork(0:)
    logical, intent(in), optional :: reverse
    type(error_t), intent(inout), optional :: err

  • private module subroutine dp_sort_index_default(array, index, work, iwork, reverse, err)

    dp_sort_index_default( array, index[, work, iwork, reverse] ) sorts an input ARRAY of type real(dp) using a hybrid sort based on the "Rust" sort algorithm found in slice.rs and returns the sorted ARRAY and an array INDEX of indices in the order that would sort the input ARRAY in the desired direction.

    Arguments

    Type IntentOptional Attributes Name
    real(kind=dp), intent(inout) :: array(0:)
    integer(kind=int_index), intent(out) :: index(0:)
    real(kind=dp), intent(out), optional :: work(0:)
    integer(kind=int_index), intent(out), optional :: iwork(0:)
    logical, intent(in), optional :: reverse
    type(error_t), intent(inout), optional :: err

  • private module subroutine dp_sort_index_low(array, index, work, iwork, reverse, err)

    dp_sort_index_low( array, index[, work, iwork, reverse] ) sorts an input ARRAY of type real(dp) using a hybrid sort based on the "Rust" sort algorithm found in slice.rs and returns the sorted ARRAY and an array INDEX of indices in the order that would sort the input ARRAY in the desired direction.

    Arguments

    Type IntentOptional Attributes Name
    real(kind=dp), intent(inout) :: array(0:)
    integer(kind=int_index_low), intent(out) :: index(0:)
    real(kind=dp), intent(out), optional :: work(0:)
    integer(kind=int_index_low), intent(out), optional :: iwork(0:)
    logical, intent(in), optional :: reverse
    type(error_t), intent(inout), optional :: err

  • private module subroutine int32_sort_index_default(array, index, work, iwork, reverse, err)

    int32_sort_index_default( array, index[, work, iwork, reverse] ) sorts an input ARRAY of type integer(int32) using a hybrid sort based on the "Rust" sort algorithm found in slice.rs and returns the sorted ARRAY and an array INDEX of indices in the order that would sort the input ARRAY in the desired direction.

    Arguments

    Type IntentOptional Attributes Name
    integer(kind=int32), intent(inout) :: array(0:)
    integer(kind=int_index), intent(out) :: index(0:)
    integer(kind=int32), intent(out), optional :: work(0:)
    integer(kind=int_index), intent(out), optional :: iwork(0:)
    logical, intent(in), optional :: reverse
    type(error_t), intent(inout), optional :: err

  • private module subroutine int32_sort_index_low(array, index, work, iwork, reverse, err)

    int32_sort_index_low( array, index[, work, iwork, reverse] ) sorts an input ARRAY of type integer(int32) using a hybrid sort based on the "Rust" sort algorithm found in slice.rs and returns the sorted ARRAY and an array INDEX of indices in the order that would sort the input ARRAY in the desired direction.

    Arguments

    Type IntentOptional Attributes Name
    integer(kind=int32), intent(inout) :: array(0:)
    integer(kind=int_index_low), intent(out) :: index(0:)
    integer(kind=int32), intent(out), optional :: work(0:)
    integer(kind=int_index_low), intent(out), optional :: iwork(0:)
    logical, intent(in), optional :: reverse
    type(error_t), intent(inout), optional :: err

  • private module subroutine int64_sort_index_default(array, index, work, iwork, reverse, err)

    int64_sort_index_default( array, index[, work, iwork, reverse] ) sorts an input ARRAY of type integer(int64) using a hybrid sort based on the "Rust" sort algorithm found in slice.rs and returns the sorted ARRAY and an array INDEX of indices in the order that would sort the input ARRAY in the desired direction.

    Arguments

    Type IntentOptional Attributes Name
    integer(kind=int64), intent(inout) :: array(0:)
    integer(kind=int_index), intent(out) :: index(0:)
    integer(kind=int64), intent(out), optional :: work(0:)
    integer(kind=int_index), intent(out), optional :: iwork(0:)
    logical, intent(in), optional :: reverse
    type(error_t), intent(inout), optional :: err

  • private module subroutine int64_sort_index_low(array, index, work, iwork, reverse, err)

    int64_sort_index_low( array, index[, work, iwork, reverse] ) sorts an input ARRAY of type integer(int64) using a hybrid sort based on the "Rust" sort algorithm found in slice.rs and returns the sorted ARRAY and an array INDEX of indices in the order that would sort the input ARRAY in the desired direction.

    Arguments

    Type IntentOptional Attributes Name
    integer(kind=int64), intent(inout) :: array(0:)
    integer(kind=int_index_low), intent(out) :: index(0:)
    integer(kind=int64), intent(out), optional :: work(0:)
    integer(kind=int_index_low), intent(out), optional :: iwork(0:)
    logical, intent(in), optional :: reverse
    type(error_t), intent(inout), optional :: err

  • private module subroutine sp_sort_index_default(array, index, work, iwork, reverse, err)

    sp_sort_index_default( array, index[, work, iwork, reverse] ) sorts an input ARRAY of type real(sp) using a hybrid sort based on the "Rust" sort algorithm found in slice.rs and returns the sorted ARRAY and an array INDEX of indices in the order that would sort the input ARRAY in the desired direction.

    Arguments

    Type IntentOptional Attributes Name
    real(kind=sp), intent(inout) :: array(0:)
    integer(kind=int_index), intent(out) :: index(0:)
    real(kind=sp), intent(out), optional :: work(0:)
    integer(kind=int_index), intent(out), optional :: iwork(0:)
    logical, intent(in), optional :: reverse
    type(error_t), intent(inout), optional :: err

  • private module subroutine sp_sort_index_low(array, index, work, iwork, reverse, err)

    sp_sort_index_low( array, index[, work, iwork, reverse] ) sorts an input ARRAY of type real(sp) using a hybrid sort based on the "Rust" sort algorithm found in slice.rs and returns the sorted ARRAY and an array INDEX of indices in the order that would sort the input ARRAY in the desired direction.

    Arguments

    Type IntentOptional Attributes Name
    real(kind=sp), intent(inout) :: array(0:)
    integer(kind=int_index_low), intent(out) :: index(0:)
    real(kind=sp), intent(out), optional :: work(0:)
    integer(kind=int_index_low), intent(out), optional :: iwork(0:)
    logical, intent(in), optional :: reverse
    type(error_t), intent(inout), optional :: err