Implementing qsort in Fortran 95

I saw that you got unblocked with your problem with the help of the comments, but let me give you some suggestions to make your implementation more modular, easy to use and modern.

Disclaimer: Some of my suggestions might need a more recent Fortran version than 95.

You can improve your timestamp type definition by providing overloads for the relational operators.

type :: timestamp
    integer :: year, month, day, hour = 0, minute = 0, second = 0
contains
    procedure, private :: eq, ne, gt, ge, lt, le
    generic :: operator(==) => eq
    generic :: operator(/=) => ne
    generic :: operator(>) => gt
    generic :: operator(>=) => ge
    generic :: operator(<) => lt
    generic :: operator(<=) => le
end type

(A subtle change there is that I have default values for hour, minute and second. So you can instantiate like this: timestamp(2021,5,22))

To get this working, you just need to provide implementations for the functions eq, ne, gt, ge, lt, le available in the module you define your type. Note that, when writing a generic type bound procedure, you must declare your bound parameter as class(timestamp) instead of type(timestamp).

elemental function lt(left, right) result(result)
    class(timestamp), intent(in) :: left, right
    logical :: result
    result = compare(left, right) < 0
end function

elemental function compare(this, other) result(result)
    class(timestamp), intent(in) :: this, other
    integer :: result
    if (this%year /= other%year) then
        result = sign(1, this%year - other%year)
    else if (this%month /= other%month) then
        result = sign(1, this%month - other%month)
    else if (this%day /= other%day) then
        result = sign(1, this%day - other%day)
    else if (this%hour /= other%hour) then
        result = sign(1, this%hour - other%hour)
    else if (this%minute /= other%minute) then
        result = sign(1, this%minute - other%minute)
    else if (this%second /= other%second) then
        result = sign(1, this%second - other%second)
    else 
        result = 0
    end if
end function

Another good practice you can implement is to control access of your module elements by using public and private.

module data_model
    implicit none
    public :: timestamp, tape
    private
    type :: timestamp
        ! (...)
    end type
    type :: tape
        type(timestamp) :: ts
        integer :: value1, value2
    end type
contains
    ! (...) implementations of eq, ne, gt, ge, lt, le
end

Then, when you use this module from another program unit, only the public names will be available. You can also use only specific name with the use only clause:

module qsort
    use data_model, only: tape
    implicit none
    public :: quicksort
    private
contains
    ! (...) your quicksort implementation
end

Finally, let me suggest some tweaks on your quicksort implementation.

First, I suggest that you don't need to pass around the boundaries lo and hi everywhere together with your array. One of the most distinctive features of Fortran is how easy it is to operate on array segments. You can call the quicksort procedure on a contiguous portion of your array, and the procedure can work on it in a boundaries-agnostic way, if you use assumed-shape arrays, like this: type(tape) :: a(:). Inside the procedure, the array segment is rebounded to start on index 1, no matter what are the bounds on the call site.

Besides that, as I mentioned in the comments, you don't need to declare the array argument as allocatable in this case. Even if the original array you are passing is originally allocatable, you can pass an allocatable array to a procedure without declaring the argument as allocatable in the procedure, it will be handled as a normal array. It only makes sense to declare the argument as allocatable if you plan to allocate/deallocate inside the procedure.

pure recursive subroutine quicksort(a)
    type(tape), intent(inout) :: a(:)
    integer :: p
    if (size(a) == 0) return
    call partition(a, p)
    call quicksort(a(:p-1))
    call quicksort(a(p+1:))
end

I declared this procedure as pure in this case, but that would depend on your specific use case. Making it pure helps me to remind declaring intents correctly and have well-though procedures (and there is a performance gain in some cases), but this brings many restrictions (like not being able to print inside the procedure). You can search for pure procedures to learn more.

Both quicksort and partition are implemented as subroutines here. I like to do this way always that the procedure performs important side-effects, like updates on the passed argument. If I need a returned value, I can have an intent(out) argument, like the argument out in partition, that returns the pivot position.

pure subroutine partition(a, out)
    type(tape), intent(inout) :: a(:)
    integer, intent(out) :: out
    integer :: i, j
    i = 1
    do j = 1, size(a)
        if (a(j)%ts < a(size(a))%ts) then
            call swap(a(i), a(j))
            i = i + 1
        end if
    end do
    call swap(a(i), a(size(a)))
    out = i
end

elemental subroutine swap(a, b)
    type(tape), intent(inout) :: a, b
    type(tape) :: temp
    temp = a
    a = b
    b = temp
end

You may note at a(j)%ts < a(size(a))%ts that I am making use of the overloaded operator < to compare two timestamp. This way, the comparison logic belongs to the same module as the type definition.

Finally, you can use the modules and make some tests on your quicksort implementation!

program main
    use data_model, only: tape, timestamp
    use qsort, only: quicksort
    implicit none

    type(tape) :: a(8) = [ &
        tape(timestamp(2020, 01, 08), 0, 0), &
        tape(timestamp(2021, 01, 30), 0, 0), &
        tape(timestamp(2020, 01, 06), 0, 0), &
        tape(timestamp(2019, 12, 14), 0, 0), & 
        tape(timestamp(2020, 01, 08), 0, 0), &
        tape(timestamp(2020, 05, 05), 0, 0), &
        tape(timestamp(2021, 04, 30), 0, 0), &
        tape(timestamp(2020, 10, 22), 0, 0) &
    ]

    call quicksort(a(3:7)) ! will sort in place, only from index 3 to 7
    call quicksort(a) ! will sort whole array
end

Works like a charm!

This is not an answer directly related to the quicksort algorithm but rather on how to implement type-bound operators.

You can move the compare function inside the data_model module. This decouples the modules further s.t. the quicksort module only contains the quicksort algorithm.

The compare function can be implemented by a type-bound operator operator(<). The following shows a quick implementation (only for year/month/day) and it should help you to edit your own code accordingly.

module timestamp_m
  implicit none

  private
  public timestamp

  type timestamp
    integer :: y, m, d
  contains
    generic            :: operator(<) => timestamp_lt
    procedure, private :: timestamp_lt
  end type

contains

  logical function timestamp_lt(this, rhs) result(tf)
    !! result of:     this < rhs
    class(timestamp), intent(in) :: this
    type(timestamp),  intent(in) :: rhs

    ! compare year
    if      (this%y < rhs%y) then
      tf = .true.
    else if (this%y > rhs%y) then
      tf = .false.
    else

      ! compare month
      if      (this%m < rhs%m) then
        tf = .true.
      else if (this%m > rhs%m) then
        tf = .false.
      else

        ! compare day
        if (this%d < rhs%d) then
          tf = .true.
        else
          tf = .false.
        end if
      end if
    end if
  end function

end module

You will need to adjust one line in your quicksort module:

module qsort
..
  subroutine quicksort(a, lo, hi)
    ..
    ! if (compare(a(j), pivot)) then      ! OLD. replace by:
    if (a(j)%ts < pivot%ts) then
    ..