pic_sorting_ord_sort Module

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

 call ord_sort( array[, work, 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.

  • work (optional): shall be a rank 1 array of the same type as array, and shall have at least size(array)/2 elements. It is an intent(out) argument to be used as “scratch” memory for internal record keeping. If associated with an array in static storage, its use can significantly reduce the stack memory requirements for the code. Its value on return is undefined.

  • 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 stable order. Otherwise index will sort array in order of non-decreasing values in stable order.

Example

    ...
    ! Read arrays from sorted files
    call read_sorted_file( 'dummy_file1', array1 )
    call read_sorted_file( 'dummy_file2', array2 )
    ! Concatenate the arrays
    allocate( array( size(array1) + size(array2) ) )
    array( 1:size(array1) ) = array1(:)
    array( size(array1)+1:size(array1)+size(array2) ) = array2(:)
    ! Sort the resulting array
    call ord_sort( array, work )
    ! Process the sorted array
    call array_search( array, values )
    ...

Uses

  • module~~pic_sorting_ord_sort~~UsesGraph module~pic_sorting_ord_sort pic_sorting_ord_sort module~pic_optional_value pic_optional_value module~pic_sorting_ord_sort->module~pic_optional_value module~pic_types pic_types module~pic_sorting_ord_sort->module~pic_types module~pic_optional_value->module~pic_types iso_fortran_env iso_fortran_env module~pic_types->iso_fortran_env

Used by

  • module~~pic_sorting_ord_sort~~UsedByGraph module~pic_sorting_ord_sort pic_sorting_ord_sort module~pic_sorting pic_sorting module~pic_sorting->module~pic_sorting_ord_sort

Variables

Type Visibility Attributes Name Initial
integer, private, parameter :: max_merge_stack = int(ceiling(log(2._dp**64)/log(1.6180339887_dp)))

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)

    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

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

    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

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

    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

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

    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

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

    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

Derived Types

type, private ::  run_type

Used to pass state around in a stack among helper functions for the ORD_SORT and SORT_INDEX algorithms

Components

Type Visibility Attributes Name Initial
integer(kind=int_index), public :: base = 0
integer(kind=int_index), public :: len = 0

Subroutines

private subroutine char_decrease_ord_sort(array, work)

Arguments

Type IntentOptional Attributes Name
character(len=*), intent(inout) :: array(0:)
character(len=len), intent(out), optional :: work(0:)

private subroutine char_increase_ord_sort(array, work)

Arguments

Type IntentOptional Attributes Name
character(len=*), intent(inout) :: array(0:)
character(len=len), intent(out), optional :: work(0:)

private module subroutine char_ord_sort(array, work, reverse)

Arguments

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

private subroutine dp_decrease_ord_sort(array, work)

Arguments

Type IntentOptional Attributes Name
real(kind=dp), intent(inout) :: array(0:)
real(kind=dp), intent(out), optional :: work(0:)

private subroutine dp_increase_ord_sort(array, work)

Arguments

Type IntentOptional Attributes Name
real(kind=dp), intent(inout) :: array(0:)
real(kind=dp), intent(out), optional :: work(0:)

private module subroutine dp_ord_sort(array, work, reverse)

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

private subroutine int32_decrease_ord_sort(array, work)

Arguments

Type IntentOptional Attributes Name
integer(kind=int32), intent(inout) :: array(0:)
integer(kind=int32), intent(out), optional :: work(0:)

private subroutine int32_increase_ord_sort(array, work)

Arguments

Type IntentOptional Attributes Name
integer(kind=int32), intent(inout) :: array(0:)
integer(kind=int32), intent(out), optional :: work(0:)

private module subroutine int32_ord_sort(array, work, reverse)

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

private subroutine int64_decrease_ord_sort(array, work)

Arguments

Type IntentOptional Attributes Name
integer(kind=int64), intent(inout) :: array(0:)
integer(kind=int64), intent(out), optional :: work(0:)

private subroutine int64_increase_ord_sort(array, work)

Arguments

Type IntentOptional Attributes Name
integer(kind=int64), intent(inout) :: array(0:)
integer(kind=int64), intent(out), optional :: work(0:)

private module subroutine int64_ord_sort(array, work, reverse)

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

private subroutine sp_decrease_ord_sort(array, work)

Arguments

Type IntentOptional Attributes Name
real(kind=sp), intent(inout) :: array(0:)
real(kind=sp), intent(out), optional :: work(0:)

private subroutine sp_increase_ord_sort(array, work)

Arguments

Type IntentOptional Attributes Name
real(kind=sp), intent(inout) :: array(0:)
real(kind=sp), intent(out), optional :: work(0:)

private module subroutine sp_ord_sort(array, work, reverse)

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