merge sort of 2 dim array

[Byoungho_Park]

I found merge sort program code from wikibook(http://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting/Merge_sort).

I'm trying to use this code for 2 dim array.

but I can't.

The following is source.

subroutine Merge(A,NA,B,NB,C,NC)

integer, intent(in) :: NA,NB,NC ! Normal usage: NA+NB = NC

integer, intent(in out) :: A(NA) ! B overlays C(NA+1:NC)

integer, intent(in) :: B(NB)

integer, intent(in out) :: C(NC)

integer :: I,J,K

I = 1; J = 1; K = 1;

do while(I <= NA .and. J <= NB)

if (A(I) <= B(J)) then

C(K) = A(I)

I = I+1

else

C(K) = B(J)

J = J+1

endif

K = K + 1

enddo

do while (I <= NA)

C(K) = A(I)

I = I + 1

K = K + 1

enddo

return

end subroutine merge

recursive subroutine MergeSort(A,N,T)

integer, intent(in) :: N

integer, dimension(N), intent(in out) :: A

integer, dimension((N+1)/2), intent (out) :: T

integer :: NA,NB,V

if (N < 2) return

if (N == 2) then

if (A(1) > A(2)) then

V = A(1)

A(1) = A(2)

A(2) = V

endif

return

endif

NA=(N+1)/2

NB=N-NA

call MergeSort(A,NA,T)

call MergeSort(A(NA+1),NB,T)

if (A(NA) > A(NA+1)) then

T(1:NA)=A(1:NA)

call Merge(T,NA,A(NA+1),NB,A,N)

endif

return

end subroutine MergeSort

program TestMergeSort

integer, parameter :: N = 8

integer, dimension(N) :: A = (/ 1, 5, 2, 7, 3, 9, 4, 6 /)

integer, dimension ((N+1)/2) :: T

call MergeSort(A,N,T)

write(*,'(A,/,10I3)')'Sorted array :',A

end program TestMergeSort

I want to sort these data.
2 4
1 2
4 8
3 6
5 9

I want the result to be sored as following.
1 2
2 4
36
4 8
5 9

Please help me!!

[mecej4]

The Wikibooks code (coincidence: I wrote that code, some years ago!) is not intended to sort an integer array when there is an associated array to be reordered.

Wikibooks code is intended to demonstrate algorithms with simple code, and efficiency of execution is not a goal. There are hundreds of programs available elsewhere that will do the task more efficiently.

Intel Fortran itself provides the QSORT library routine (this is not merge sort, most likely), with an example in which the associated data is CHARACTER(len=10). It should be easy for you to adapt the example source code for the case when the associated data is of type INTEGER.

[SergeyKostrov]

- Quick Sort algorithm is the best choice in case of anarray with asizeless than 8MB.

- Pegionhole Sort algorithm is the best choice to sort an array of integers.In case oflarge integerarrays
( greater than 8MB ) it easilyoutperformsQuick, Heap and Merge sortingalgorithms.

Best regards,
Sergey

[Byoungho_Park]

My goal is that I want to sort character(len=16) 2 dim arrary.
Perhaps array size is 4,000,000 * 2.
In the liunx shell, it takes short time to sort this kind of array.
I read that linux sort program uses merge sort algorithm.
So I'm looking into the merge sort algorithm from the internet.
But I can't change the code for 2 dim array.

[mecej4 · Accepted solution]

It is incorrect, and causes confusion, to say that you want to sort a two-dimensional array. You want to sort a table with two columns, the sort keys being the contents first column, with the second column containing the associated data.

It is easy to adapt the Wikibooks code to include an associated array. Below, for example, is code to sort a two-column table of integers, with the first column holding the key.

Note that this code is NOT production code. In particular, production code would switch from mergesort to insertion sort for subfiles shorter than a threshold such as N = 16. If this feature is provided, the code will run much faster.

It should be a good exercise for you to modify the program to handle a table the columns of which are of type character(len=nn) instead of type integer.

[fortran]MODULE srtmod TYPE ipair INTEGER :: v ! sort key INTEGER :: a ! associated data END TYPE END MODULE srtmod subroutine Merge(A,NA,B,NB,C,NC) use srtmod integer, intent(in) :: NA,NB,NC ! Normal usage: NA+NB = NC type(ipair), intent(in out) :: A(NA) ! B overlays C(NA+1:NC) type(ipair), intent(in) :: B(NB) type(ipair), intent(in out) :: C(NC) integer :: I,J,K I = 1; J = 1; K = 1; do while(I <= NA .and. J <= NB) if (A(I)%v <= B(J)%v) then C(K) = A(I) I = I+1 else C(K) = B(J) J = J+1 endif K = K + 1 enddo do while (I <= NA) C(K) = A(I) I = I + 1 K = K + 1 enddo return end subroutine merge recursive subroutine MergeSort(A,N,T) use srtmod integer, intent(in) :: N type(ipair), dimension(N), intent(in out) :: A type(ipair), dimension((N+1)/2), intent (out) :: T integer :: NA,NB type(ipair) :: VT if (N < 2) return if (N == 2) then if (A(1)%v > A(2)%v) then VT = A(1) A(1) = A(2) A(2) = VT endif return endif NA=(N+1)/2 NB=N-NA call MergeSort(A,NA,T) call MergeSort(A(NA+1),NB,T) if (A(NA)%v > A(NA+1)%v) then T(1:NA)=A(1:NA) call Merge(T,NA,A(NA+1),NB,A,N) endif return end subroutine MergeSort program TestMergeSort use srtmod integer :: i,N type(ipair), dimension(:), allocatable :: A , T read (*,*) N allocate (A(N),T((N+1)/2)) read(*,*)(A(i)%v,A(i)%a,i=1,N) call MergeSort(A,N,T) write(*,'(A)')' Sorted Data:' write(*,'(/,(2I2))')(A(i)%v,A(i)%a,i=1,N)
end program TestMergeSort [/fortran]