# Merge sorting

1. Oct 26, 2007

### Soff

I'm trying to write a Merge Sort program with fortran 90. However, this is what I already could do:

Code (Text):
program sorting

integer :: i,ialloc,error,n,d
integer, pointer :: a(:)

Print *,'How many numbers would you like to type in?'

Print*,' Enter the values, separated by commas'

!Result
call Merge(a,b,c,m,n)
print *,'Sorted list:'
write(*,*) (a(i),i=0,n-1)
print *,' '

end program sorting

!Merge Sorting of a() of dimension m and b() of dimension n
!into c() of size m+n=d
Subroutine Merge(a,b,c,m,n)

integer :: m,n,a(0:m-1),b(0:n-1),c(0:m+n-1)
integer :: i,j,k,d
i=0; j=0; k=0 !Start
do while (i<m.and.j<n)
if (a(i)<b(j)) then
c(k)=a(i)
i=i+1
else
c(k)=b(j)
j=j+1
end if
k=k+1
end do
do while (i<m)  !pick up any remainder
c(k)=a(i)
k=k+1; i=i+1
end do
do while (j<n)
c(k)=b(j)
k=k+1; j=j+1
end do
return
End

It starts as it was planed, but after typing in the numbers, I get an error message. So, can anyone help me? Where is the bug?

2. Oct 29, 2007

### Soff

Okay, I started again. This is my improved version (but still not working!):

Code (Text):

program sorting

integer :: d,length,center,t,i,n,m
integer :: a(128), b(128)

!List of numbers
Print *,'How many numbers would you like to type in?'

Print*,' Enter the values, separated by commas'

length=d

i=1
do while (length>=2)

length=length/2
i=i+1
end do

write(*,*)i,length
n=1

do while (n<=i)
if (a(2*n)>a(2*n-1)) then
b(2*n)=a(2*n)
b(2*n-1)=a(2*n-1)
else
b(2*n)=a(2*n-1)
b(2*n-1)=a(2*n)
end if
n=n+1
end do

write(*,*)(b(t),t=1,d)

a(i)=b(i)

n=1
m=1
length=length*2

do while (n<=i/2)
do while (m<=length-1.and.a(length*n)>=a(length*n-m))
m=m+1
end do
b(n*length-length-1-m)=a(length*n)
do while (m<=length-1.and.a(length*n-1)>=a(length*n-m))
m=m+1
end do
b(n*length-length-1-m)=a(length*n-1)
do while (m<=length-1.and.a(length*n-2)>=a(length*n-m))
m=m+1
end do
b(n*length-length-1-m)=a(length*n-1)
do while (m<=length-1.and.a(length*n-3)>=a(length*n-m))
m=m+1
end do
n=n+1
end do

write(*,*)(b(t),t=1,d)
end program

3. Oct 29, 2007

### rcgldr

In the first example, you're not sorting but merging "a" and "b" to create "c". "b" is never initialized, and you're printing "a", instead of the output, "c".

Sort algorithms (plus links to zips of source code) were discussed in this thread:

efficient sorting

Here is a direct link to the sorts that sort an array (vector) of 64 bit integers, msort.cpp is a merge sort.

sortv.zip

My merge sort is pointer oriented, if I get the time, I'll make a duplicate that uses indexes instead.