pic_sorting_radix_sort Module

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

 call radix_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). 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. Especially, -0.0 is lesser than 0.0.

  • work (optional): shall be a rank 1 array of the same type as array, and shall have at least size(array) elements. It is an intent(inout) argument to be used as buffer. Its value on return is undefined. If it is not present, radix_sort will allocate a buffer for use, and deallocate it before return. If you do several similar radix_sorts, reusing the work array is a good parctice. This argument is not present for int8_radix_sort because it use counting sort, so no buffer is needed.

  • 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 random data from a file
    call read_file( 'dummy_file', array )
    ! Sort the random data
    call radix_sort( array )
    ...

Uses

  • module~~pic_sorting_radix_sort~~UsesGraph module~pic_sorting_radix_sort pic_sorting_radix_sort module~pic_optional_value pic_optional_value module~pic_sorting_radix_sort->module~pic_optional_value module~pic_types pic_types module~pic_sorting_radix_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_radix_sort~~UsedByGraph module~pic_sorting_radix_sort pic_sorting_radix_sort module~pic_sorting pic_sorting module~pic_sorting->module~pic_sorting_radix_sort

Variables

Type Visibility Attributes Name Initial
integer, private, parameter :: radix_bits = 8
integer(kind=int32), private, parameter :: radix_bits_i32 = 8_int32
integer(kind=int64), private, parameter :: radix_bits_i64 = 8_int64
integer, private, parameter :: radix_mask = 255
integer(kind=int32), private, parameter :: radix_mask_i32 = 255_int32
integer(kind=int64), private, parameter :: radix_mask_i64 = 255_int64

Interfaces

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)

    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

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

    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

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

    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

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

    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

Subroutines

private module subroutine dp_radix_sort(array, work, reverse)

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

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

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

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

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

private pure subroutine radix_sort_u32_helper(N, arr, buf)

Arguments

Type IntentOptional Attributes Name
integer(kind=int_index), intent(in) :: N
integer(kind=int32), intent(inout), dimension(N) :: arr
integer(kind=int32), intent(inout), dimension(N) :: buf

private pure subroutine radix_sort_u64_helper(N, arr, buffer)

Arguments

Type IntentOptional Attributes Name
integer(kind=int_index), intent(in) :: N
integer(kind=int64), intent(inout), dimension(N) :: arr
integer(kind=int64), intent(inout), dimension(N) :: buffer

private module subroutine sp_radix_sort(array, work, reverse)

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