I have the following implementation of the MergeSort algorithm in Fortran.
My question is about call merge(work(1 : half), A(half + 1:), A).
Obviously I have overlapping memory, but from looking at the code in merge, this should be no problem, as long as the input arrays are sorted. (Which they are assumed to be anyway.)
On the other hand Fortran compilers may assume non aliased memory, so I always think "don't do this".
I have two questions now:
- When and how can I run into problems with my
mergesubroutine. - If I cannot implement
MergeSortlike this, how do I do it without creating a temporary array.
!> Merge sorted arrays A and B into C while preversing order.
subroutine merge(A, B, C)
implicit none
integer, intent(in) :: A(:), B(:)
integer, intent(inout) :: C(:)
integer :: i, j, k
if (size(A) + size(B) > size(C)) abort
i = 1; j = 1
do k = 1, size(C)
if (i <= size(A) .and. j <= size(B)) then
if (A(i) <= B(j)) then
C(k) = A(i)
i = i + 1
else
C(k) = B(j)
j = j + 1
end if
else if (i <= size(A)) then
C(k) = A(i)
i = i + 1
else if (j <= size(B)) then
C(k) = B(j)
j = j + 1
end if
end do
end subroutine merge
recursive subroutine MergeSort(A, work)
implicit none
integer, intent(inout) :: A(:)
integer, intent(inout) :: work(:)
integer :: half
half = (size(A) + 1) / 2
if (size(A) < 2) then
continue
else if (size(A) == 2) then
call naive_sort(A)
else
call MergeSort(A( : half), work)
call MergeSort(A(half + 1 :), work)
if (A(half) > A(half + 1)) then
work(1 : half) = A(1 : half)
! TODO: Non aliasing rule.
call merge(work(1 : half), A(half + 1:), A)
endif
end if
end subroutine MergeSort
PS: As you perhaps notice, the array C in the merge subroutine is declared as an inout parameter, because it is later used with overlapping memory.