Merge Sorting

[Developer]

Back in the good old days of the 1960 there was a routine in Fortran 66 that could take data from one tape, sort it in chunks and send the result to another tape. It would then open the new tape and merge the files into new sorted files on another tape. This was repeated until all of the chunks were merged back together.

 

Sometimes the data came from punch cards and read into a tape as well.

 

Anyone got any old FORTRAN from this era doing this stuff?

 

--
http://contract-developer.dyndns.biz

[makyo]

Hi.

The nearest I could come was code from "Software Tools", Kernighan and
Plauger, around page 117. The code is in ratfor, but should be easily
translatable into (say) f77. It will require some associated support
routines. I seem to recall doing the translation as I typed (from
ratfor to Minnesota mnf / m77). I also recall from those days that
the computer center ran 2 OSs on the CDC 1604, the first was a fast
Fortran-only system, primarily for student use. The other was CDC's
"COOP Monitor", which allowed access to other languages: Algol, COBOL,
etc. It was far more "file-oriented" than the student system. I
don't recall file sorting routines on either system, but there were
probably some associated with COBOL, as was the case with the later
CDC 6600.

Knuth Vol 3 has a long section on "External Sorting" (I found a punch
card bookmark in my copy!) including a section on "Two Tape Sorting".

Good luck ... cheers, makyo

[Steve Lionel]

makyo wrote:

> Knuth Vol 3 has a long section on "External Sorting" (I found a punch
> card bookmark in my copy!) including a section on "Two Tape Sorting".

If I recall correctly, Knuth removed all the text about tape sorting
from current editions of Vol. 3, saying it was no longer relevant.

--
Steve Lionel
Developer Products Division
Intel Corporation
Nashua, NH

For email address, replace "invalid" with "com"

User communities for Intel Software Development Products
http://software.intel.com/en-us/forums/
Intel Software Development Products Support
http://software.intel.com/sites/support/
My Fortran blog
http://www.intel.com/software/drfortran

[nm...@cam.ac.uk]

In article <7bacu7F...@mid.individual.net>,

Steve Lionel <steve....@intel.invalid> wrote:
>makyo wrote:
>
>> Knuth Vol 3 has a long section on "External Sorting" (I found a punch
>> card bookmark in my copy!) including a section on "Two Tape Sorting".
>
>If I recall correctly, Knuth removed all the text about tape sorting
>from current editions of Vol. 3, saying it was no longer relevant.

There probably are still uses for the techniques, but there are also
probably more flint-knappers than people who program tape sorts :-)

Regards,
Nick Maclaren.

[glen herrmannsfeldt]

Steve Lionel <steve....@intel.invalid> wrote:
< makyo wrote:

<> Knuth Vol 3 has a long section on "External Sorting" (I found a punch
<> card bookmark in my copy!) including a section on "Two Tape Sorting".

< If I recall correctly, Knuth removed all the text about tape sorting
< from current editions of Vol. 3, saying it was no longer relevant.

Some of the algorithms were tape specific, and I suppose it makes
sense to remove them. Others are just as applicable to external
sorting on disk, and presumably stay.

I still have my first edition Volume 3, though.

Otherwise, I wouldn't be surprised if there were assembly sort
routines available for most machines in the early days. It was
a common enough operation. I know there was a sort/merge routine
for OS/360, source is still available.

-- glen

-- glen

[Omaha]

On Jul 2, 10:36 pm, "Developer" <ab...@abuse.org> wrote:

Here is a link to an efficient text file sorting routine:

http://www.fortran.com/lcpsort.f95

It is, however, written in Fortran 95, reads a single input file in
one gulp and writes a single output file. It is definitely not tape-
oriented.

-- mecej4

[Terence]

I wrote about this here, a year ago.
I have a general purpose 15-key sort merge written in F77 (of course).
It uses one input for sort and two inputs for merge, with one output.
If the input file has long records and you want a fast sort, you
should form shorter records of just the keys plus the address of the
actual record (the only way for variable length sorting) and sort
these key ("TAG") records, then use the sorted key file to pass the
original long records in order to the output, using a form of direct
access and deblocking the needed records.

The overall sort/merge method is simple: just sort chunks in memory
with a heap sort and write sorted blocks to as many files as possible;
then merge these external files to one file then repeat. Merging two
pre-sorted files is a simple one-pass.

If you don't find a convenient solution I can send the source.

[Frank]

I did a bunch of sorts recently in fortran, and the merge sort was
conspicuously absent. If you can get a good implementation, make an
entry on the wiki or at fortran.com.

[mecej4]

>"Frank" <mer...@lomas-assault.net> wrote in message
>news:56ce1866-35f9-4439-9a30-> >
> c9fde2...@y19g2000yqy.googlegroups.com...

> On Jul 2, 8:36 pm, "Developer" <ab...@abuse.org> wrote:
> Back in the good old days of the 1960 there was a routine in Fortran 66
> that could take >data from one tape, sort it in chunks and send the result
> to another tape. It would then >open the new tape and merge the files into
> new sorted files on another tape. This was >repeated until all of the
> chunks were merged back together.
>

>I did a bunch of sorts recently in fortran, and the merge sort was
>conspicuously absent. If you can get a good implementation, make an
>entry on the wiki or at fortran.com.

For sorting an array of integers:

http://rosettacode.org/wiki/Merge_sort#Fortran

For sorting lines of text:

http://www.fortran.com/lcpsort.f95

HTH

[James Van Buskirk]

"mecej4" <mecej4@_no_spam_at_operamail.com> wrote in message
news:h39kps$ehe$1...@news.eternal-september.org...

> For sorting an array of integers:

> http://rosettacode.org/wiki/Merge_sort#Fortran

Why don't you use a generic version?

C:\gfortran\clf\mergesort>type mergesort.f90
subroutine Merge(QA,NA,QB,NB,QC,NC)

integer, intent(in) :: NA,NB,NC ! Normal usage: NA+NB = NC
intent(in out) :: QA ! QB overlays QC(NA+1:NC)
dimension QA(NA)
intent(in) :: QB
dimension QB(NB)
intent(in out) :: QC
dimension QC(NC)

integer :: I,J,K

I = 1; J = 1; K = 1;
do while(I <= NA .and. J <= NB)
if (QA(I) <= QB(J)) then
QC(K) = QA(I)
I = I+1
else
QC(K) = QB(J)
J = J+1
endif
K = K + 1
enddo
do while (I <= NA)
QC(K) = QA(I)
I = I + 1
K = K + 1
enddo
return

end subroutine merge

recursive subroutine MergeSort_template(QA,N,QT)

integer, intent(in) :: N
intent(in out) :: QA
dimension QA(N)
intent (out) :: QT
dimension QT((N+1)/2)

integer :: NA,NB

if (N < 2) return
if (N == 2) then
if (.NOT.(QA(1) <= QA(2))) then
! Had to change so that implicit character(*) (Q) would work!
! QV = QA(1)
! QA(1) = QA(2)
! QA(2) = QV
QA((/1,2/)) = QA((/2,1/))
endif
return
endif
NA=(N+1)/2
NB=N-NA

call MergeSort_template(QA,NA,QT)
call MergeSort_template(QA(NA+1),NB,QT)

if (.NOT.(QA(NA) <= QA(NA+1))) then
QT(1:NA)=QA(1:NA)
call Merge(QT,NA,QA(NA+1),NB,QA,N)
endif
return

end subroutine MergeSort_template

C:\gfortran\clf\mergesort>type test.f90
module integer_mod
implicit integer(Q)
private
public Mergesort
interface Mergesort
module procedure Mergesort_template
end interface Mergesort
contains
include 'mergesort.f90'
end module integer_mod

module real_mod
implicit real(Q)
private
public Mergesort
interface Mergesort
module procedure Mergesort_template
end interface Mergesort
contains
include 'mergesort.f90'
end module real_mod

module character_mod
implicit character(len=*) (Q)
private
public Mergesort
interface Mergesort
module procedure Mergesort_template
end interface Mergesort
contains
include 'mergesort.f90'
end module character_mod

module mytype_def
implicit none
type mytype
integer X
end type mytype
interface assignment(=)
module procedure assign
end interface assignment(=)
interface operator(<=)
module procedure less_than_or_equals
end interface operator(<=)
contains
elemental subroutine assign(x, y)
type(mytype), intent(out) :: x
type(mytype), intent(in) :: y

x%X = y%X
end subroutine assign

function less_than_or_equals(x,y)
logical less_than_or_equals
type(mytype), intent(in) :: x, y

less_than_or_equals = x%X <= y%X
end function less_than_or_equals
end module mytype_def

module mytype_mod
use mytype_def
implicit type(mytype) (Q)
private
public Mergesort
interface Mergesort
module procedure Mergesort_template
end interface Mergesort
contains
include 'mergesort.f90'
end module mytype_mod

module generic_recombination
use integer_mod
use real_mod
use character_mod
use mytype_mod
end module generic_recombination

program TestMergeSort
use generic_recombination
use mytype_def
implicit none

integer, parameter :: N = 8
integer, dimension(N) :: A = (/ 1, 5, 2, 7, 3, 9, 4, 6 /)
integer, dimension ((N+1)/2) :: T
real, dimension(N) :: B = (/ 1, 5, 2, 7, 3, 9, 4, 6 /)
real, dimension ((N+1)/2) :: U
character(7), dimension(N) :: C = 'string'//achar(48+(/1,5,2,7,3,9,4,6/))
character(7), dimension ((N+1)/2) :: V
type(mytype), dimension(N) :: D = (/ mytype(1), mytype(5), &
mytype(2), mytype(7), mytype(3), mytype(9), mytype(4), mytype(6) /)
type(mytype), dimension ((N+1)/2) :: W

call MergeSort(A,N,T)
write(*,'(A,/,10I3)')'Sorted integer array :',A

call MergeSort(B,N,U)
write(*,'(/A,/,10(f0.1:1x))')'Sorted real array :',B

call MergeSort(C,N,V)
write(*,'(/A,/,10(A:1x))')'Sorted character array :',C

call MergeSort(D,N,W)
write(*,'(/A,/,10I3)')'Sorted UDT array :',D

end program TestMergeSort

C:\gfortran\clf\mergesort>gfortran test.f90 -otest

C:\gfortran\clf\mergesort>test
Sorted integer array :
1 2 3 4 5 6 7 9

Sorted real array :
1.0 2.0 3.0 4.0 5.0 6.0 7.0 9.0

Sorted character array :
string1 string2 string3 string4 string5 string6 string7 string9

Sorted UDT array :
1 2 3 4 5 6 7 9

--
write(*,*) transfer((/17.392111325966148d0,6.5794487871554595D-85, &
6.0134700243160014d-154/),(/'x'/)); end

[Frank]

On Jul 11, 2:03 am, "mecej4" <mecej4@_no_spam_at_operamail.com> wrote:
> >"Frank" <merr...@lomas-assault.net> wrote in message
> >news:56ce1866-35f9-4439-9a30-> >
> > c9fde28f4...@y19g2000yqy.googlegroups.com...

> > On Jul 2, 8:36 pm, "Developer" <ab...@abuse.org> wrote:
> > Back in the good old days of the 1960 there was a routine in Fortran 66
> > that could take >data from one tape, sort it in chunks and send the result
> > to another tape. It would then >open the new tape and merge the files into
> > new sorted files on another tape. This was >repeated until all of the
> > chunks were merged back together.
>
> >I did a bunch of sorts recently in fortran, and the merge sort was
> >conspicuously absent.  If you can get a good implementation, make an
> >entry on the wiki or at fortran.com.
>
> For sorting an array of integers:
>
>    http://rosettacode.org/wiki/Merge_sort#Fortran
>
> For sorting lines of text:
>
>    http://www.fortran.com/lcpsort.f95
>
> HTH

Nice, Tom, this looks like a good project for when I start up with
fortran source again. If I stay away for long enough, maybe all my
head-scratchers will bw on the wiki. :)

[mecej4]

"James Van Buskirk" <not_...@comcast.net> wrote in message
news:h3aipi$bgh$1...@news.eternal-september.org...

> "mecej4" <mecej4@_no_spam_at_operamail.com> wrote in message
> news:h39kps$ehe$1...@news.eternal-september.org...
>
>> For sorting an array of integers:
>
>> http://rosettacode.org/wiki/Merge_sort#Fortran
>
> Why don't you use a generic version?

Excellent suggestion, but:

(i) RosettaCode is more oriented towards comparing between languages
than comprehensiveness or efficiency (my dark side says it is a cheat site
for students). Fortran was rather underrepresented, a situation that I tried
to start rectifying. In this situation, I felt that I needed to make a
compromise between code length and versatility.

(ii) Please jump in and change/add to the collection at RosettaCode and
WikiBooks.

(iii) The string version of mergesort at fortran.com is quite a bit
specialized: it uses the Longest Common Prefix Length enhancement for speed.

I had problems with your code with any but the latest compilers.
gFortran-4.3.2 and Lahey 7.1 failed to compile it, the former with an ICE
and the latter saying:

Module subprogram name(MergeSort_template)
2523-S: "mergesort.f90", line 50: Actual argument associated with dummy
argument
'assign' must be definable when dummy argument has the
INTENT(OUT) or
INTENT(INOUT) attribute.

IFC 9.1.28 ran the program, but the result for the string sort was

string1 string5 string2 string7 string3 string9 string4 string6

I have not yet tried to find out why.

Thanks.

-- mecej4

[James Van Buskirk]

"mecej4" <mecej4@_no_spam_at_operamail.com> wrote in message

news:h3bii2$mt$1...@news.eternal-september.org...

> I had problems with your code with any but the latest compilers.
> gFortran-4.3.2 and Lahey 7.1 failed to compile it, the former with an ICE
> and the latter saying:

> Module subprogram name(MergeSort_template)
> 2523-S: "mergesort.f90", line 50: Actual argument associated with dummy
> argument
> 'assign' must be definable when dummy argument has the
> INTENT(OUT) or
> INTENT(INOUT) attribute.

Oh, I think that is the line:

QA((/1,2/)) = QA((/2,1/))

Definitely should have been caught by gfortran but isn't even with
-std=f95 in force. The problem is that in the user-defined type
version, it's equivalent to:

call assign(QA((/1,2/)), (QA((/2,1/))))

and QA((/1,2/)) is not definable. This can be fixed by changing
to:

QA(1:2) = QA((/2,1/))

ISTR that older versions of gfortran might have had some sort of
problem with implicit character(*) (Q) which is not surprising
because character(*) can mean two completely different things:

1) It could be a dummy argument or function result whose LEN
is determined by the caller, or
2) It could a a character constant whose LEN is determined by
that of its initialization expression.

But gfortran seems to be OK with it now:

C:\gfortran\clf\mergesort>type charstartest.f90
program charstartest
implicit character(*) (Q)
parameter(Q1 = 'This is Q1')
character(10) Q2

write(*,*) Q1
write(*,*) Q2(Q1)
end program charstartest

function Q2(Q1)
implicit character(*) (Q)

Q2 = 'This is Q2'
end function Q2

C:\gfortran\clf\mergesort>gfortran charstartest.f90 -ocharstartest

C:\gfortran\clf\mergesort>charstartest
This is Q1
This is Q2

> IFC 9.1.28 ran the program, but the result for the string sort was

> string1 string5 string2 string7 string3 string9 string4 string6

> I have not yet tried to find out why.

I expect it's barfing on the fateful line 50 here. ifort tries to
get too fancy with elemental assignment...

Oops, last minute edit: bad diagnosis, actually this says the
original input is unchanged by ifort. Well, it's not that important
if it works with the current version. I would like to see whether
it does or not. I would have thought ifort would have died on
the user-defined type version.

[Frank]

On Jul 11, 7:36 pm, "mecej4" <mecej4@_no_spam_at_operamail.com> wrote:
> "James Van Buskirk" <not_va...@comcast.net> wrote in messagenews:h3aipi$bgh$1...@news.eternal-september.org...

> > 6.0134700243160014d-154/),(/'x'/)); end- Hide quoted text -
>
> - Show quoted text -

[can't snip for reasons unknown]

(iii) The string version of mergesort at fortran.com is quite a
bit
specialized: it uses the Longest Common Prefix Length enhancement for
speed.

Can you highlight this code?

[Terence]

Some comments on the postings, without being too specific:-

The suggestions made all seem to deal with just one or another kind of
field type and not mixed field types in the keys. I myself limited my
own key number limit to 15 since I never found a case that needed near
that many (mostly working with census data).
.
Nor did I see any indication of dealing with the considerable number
of files needed for large numbers of records (total byte size is not
that important until file addressing limits loom; it's the number of
reords that's important).

And the source for a general internal-plus-external sort merge is
really not as large as implied by the examples, except when dealing
with variable length records, when a tag sort has to be used,
followed by a somewhat slowerr direct access final file construction.

I never got around to working on a time-saving algorithm for that
reconstruction; but I suspect it has the framework of yet another sort
to block the subsets of access areas.

Over the near-30 years I needed to sort files, I found I had to
manage the following key types:- character strings (non-case
dependent), big-ended hex (for unsigned binary), signed binary fixed
as 2 and 4 byte (higher uses the components in order), float as 4 and
8 byte; all with independent ascending and descending orders. I never
got to need Logical and dates can be broken up in pieces to match
representations.

Even if you don't need to sort, Knuth's "Sorting and Searching" is
well worth the read.

.

the regarslvery multiple (and even simple internal-only in or
recordtHE SUGGESTIONS MADE ALL SEEM TO DEAL WOTH ONE KIND OF FI

[mecej4]

"Frank" <mer...@lomas-assault.net> wrote in message

news:58a85136-231d-4ad7...@u16g2000pru.googlegroups.com...

On Jul 11, 7:36 pm, "mecej4" <mecej4@_no_spam_at_operamail.com> wrote:
> "James Van Buskirk" <not_va...@comcast.net> wrote in
> messagenews:h3aipi$bgh$1...@news.eternal-september.org...
>
> > "mecej4" <mecej4@_no_spam_at_operamail.com> wrote in message
> >news:h39kps$ehe$1...@news.eternal-september.org...
>

<---CUT--->

>> (iii) The string version of mergesort at fortran.com is quite a
>> bit specialized: it uses the Longest Common Prefix Length enhancement for
>> speed.

> Can you highlight this code?

What do you mean? The source code is a text file. You can highlight it any
way you want.

The LLCP algoritm is described very well in

http://www.jstage.jst.go.jp/article/ipsjdc/4/0/4_69/_article

and in the PDF file to which a link is provided there.

See also

http://code.google.com/p/string-sorting/wiki/References

-- mecej4

[Frank]

On Jul 11, 7:36 pm, "mecej4" <mecej4@_no_spam_at_operamail.com> wrote:

> "James Van Buskirk" <not_va...@comcast.net> wrote in messagenews:h3aipi$bgh$1...@news.eternal-september.org...

>
> > "mecej4" <mecej4@_no_spam_at_operamail.com> wrote in message
> >news:h39kps$ehe$1...@news.eternal-september.org...
>
> >> For sorting an array of integers:
>
> >>    http://rosettacode.org/wiki/Merge_sort#Fortran
>
> > Why don't you use a generic version?
>
> Excellent suggestion, but:
>
>     (i) RosettaCode is more oriented towards comparing between languages
> than comprehensiveness or efficiency (my dark side says it is a cheat site
> for students). Fortran was rather underrepresented, a situation that I tried
> to start rectifying. In this situation, I felt that I needed to make a
> compromise between code length and versatility.

I tried to adapt this to reals, but my mergesort doesn't sort :(

F:\gfortran\dan>gfortran merge8.f90 -Wall -O2 -o t.exe

F:\gfortran\dan>t
1.00000000 1.00000000 1.1500000 1.00000000
1.1000000
1.2500000 1.00000000 1.4000000 1.00000000
1.3500000
1.5000000 1.00000000 1.6500000 1.00000000
1.6000000
1.7500000 1.00000000 1.9000000 1.00000000
1.8500000

2.0500000 2.0999999 2.1500001 2.2000000
2.2500000
2.3000000 2.3499999 2.4000001 2.4500000
2.5000000
2.5500000 2.5999999 2.6500001 2.7000000
2.7500000
2.8000000 2.8499999 2.9000001 2.9500000
3.0000000

2.0161083 2.0000000 2.0737543 2.0000000
2.0053551
2.1331604 2.0000000 2.3229873 2.0000000
2.3422437
2.0000000 2.3673909 2.0000000 2.3867660
2.4454823
2.5668247 2.0000000 2.6508548 2.9005246
2.9659152

20 0.0000E+00 0.0000E+00 0.0000E+00 0.0000E+00 0.0000E+00
0.0000E+00

F:\gfortran\dan>type merge8.f90

program sortdriver

implicit none

integer i, j, k
real, allocatable :: a(:), b(:), t(:)
real t0, t1, t2, t3, t4, t5, t6, t7, t8, t9, t10, t11

do j = 1, 1

k = 20 * j

allocate(a(k), b(k), t((k+1)/2))

! Descending
do i = 1, k
a(i) = 2 - real(i) / real(k)
end do

b = a

call cpu_time(t0)
call bubble_sort(a)
call cpu_time(t1)
t1 = t1 - t0

call cpu_time(t0)
call MergeSort(b, k, t)
call cpu_time(t2)
t2 = t2 - t0
print *, b

! Ascending
do i = 1, k
a(i) = 2 + real(i) / real(k)
end do

b = a

call cpu_time(t0)
call bubble_sort(a)
call cpu_time(t3)
t3 = t3 - t0

call cpu_time(t0)
call MergeSort(b, k, t)
call cpu_time(t4)
t4 = t4 - t0
print *, b

call random_number(a)
a = 2 + a
b = a

call cpu_time(t0)
call bubble_sort(a)
call cpu_time(t5)
t5 = t5 - t0

call cpu_time(t0)
call MergeSort(b, k, t)
call cpu_time(t6)
t6 = t6 - t0
print *, b

write(*,'(i0,1x,6es12.4)') k, t1, t2, t3, t4, t5, t6

deallocate(a, b, t)

end do

contains
subroutine bubble_sort(a)
! simple bubble sort.
implicit none
real, intent(inout) :: a(:)
real :: temp
integer :: m, n
do m = (size(a)-1), 1, -1
do n = m, (size(a)-1)
if (a(n) .le. a(n+1)) exit
temp = a(n+1)
a(n+1) = a(n)
a(n) = temp
end do
end do
return
end subroutine bubble_sort

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

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

real, intent(in out) :: A(NA)
! B overlays C(NA+1:NC)
real, intent(in) :: B(NB)
real, 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
real, dimension(N), intent(in out) :: A
real, 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

end program sortdriver

! gfortran merge8.f90 -Wall -O2 -o t.exe

Here's the template I used for the kind conversion:

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

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

zax, intent(in out) :: A(NA)
! B overlays C(NA+1:NC)
zax, intent(in) :: B(NB)
zax, 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
zax, dimension(N), intent(in out) :: A
zax, 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 = 4
zax, dimension(N) :: A = (/ 2.5, 1.0, 3.7, 0.5/)
zax, dimension ((N+1)/2) :: T
call MergeSort(A,N,T)
print *, A
end program TestMergeSort

! gfortran merge6.f90 -Wall -O2 -o r.exen>

What did I miss?

[Ron Shepard]

In article
<1ffb5c45-506e-4e1a...@t11g2000prh.googlegroups.com>,
Frank <mer...@lomas-assault.net> wrote:

[...]

> I tried to adapt this to reals, but my mergesort doesn't sort :(

[...]

> if (A(1) > A(2)) then
> V = A(1)
> A(1) = A(2)
> A(2) = V
> endif

[...]
> What did I miss?

Here's one thing I noticed.

V is declared integer, A(*) is declared real.

$.02 -Ron Shepard

[Frank]

On Jul 17, 2:42 pm, Ron Shepard <ron-shep...@NOSPAM.comcast.net>
wrote:
> In article
> <1ffb5c45-506e-4e1a-a866-1127e38e3...@t11g2000prh.googlegroups.com>,

>
>  Frank <merr...@lomas-assault.net> wrote:
>
> [...]
>
> > I tried to adapt this to reals, but my mergesort doesn't sort :(
> [...]
> > if (A(1) > A(2)) then
> >   V = A(1)
> >   A(1) = A(2)
> >   A(2) = V
> > endif
> [...]
> > What did I miss?
>
> Here's one thing I noticed.
>
> V is declared integer, A(*) is declared real.
>
> $.02 -Ron Shepard

I think that's going to be it, Ron. When I get stuck, my best course
is to walk away for a priod of time that includes a full night's
sleep. There was nothing real for a swap.

How hard would it be to extend that template to character data?

[mecej4]

"Frank" <mer...@lomas-assault.net> wrote in message news:2fdfbd5e-34c4-4b3d...@y4g2000prf.googlegroups.com...

<--CUT-->

> I think that's going to be it, Ron. When I get stuck, my best course
> is to walk away for a priod of time that includes a full night's
> sleep. There was nothing real for a swap.

> How hard would it be to extend that template to character data?

James van Buskirk posted working code in this thread that did exactly that.

-- mecej4

[Frank]

On Jul 11, 10:54 pm, "James Van Buskirk" <not_va...@comcast.net>
wrote:

This seems to be a work in progress.

I'll work it up in perl again with a new data set.