Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Merge sorting

  1. Oct 26, 2007 #1
    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?'
    Read(*,*)d

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

    Read(*,*)(a(t),t=1, d)

    !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. jcsd
  3. Oct 29, 2007 #2
    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?'
    Read(*,*)d

    Print*,' Enter the values, separated by commas'
    Read(*,*)(a(t),t=1, d)


    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
     
  4. Oct 29, 2007 #3

    rcgldr

    User Avatar
    Homework Helper

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Merge sorting
  1. Sorting algorithm? (Replies: 2)

  2. Perfect sort (Replies: 2)

  3. Merge sort (Replies: 1)

  4. Merge sort help (Replies: 2)

Loading...