Re: sorting large numbers of large records

["John Cupak" <jcupak744@comcast.net>]

As much as I just LOVE Ada, this reminds me of my favorite interview
questions
a few years back - which might just solve Brien's problems.

"Well, young man," I used to ask, "how would you sort 20 records?"

The interviewee would typically respond "I'd use the bubble sort."

I'd listen to his answer, and then ask "and how would you sort 1000
records?"

They'd stumble around on that one for a bit, until they remembered something
about the quick sort, and propose to use that algorithm.

Then I'd spring the final question. "How would you sort 1,000,000 records?"

They'd scratch their heads and usually offer the quick sort again.

But, if someone answered "I'd call the system sort routine" for EVERY
question,
 then I knew I was interviewing a COBOL programmer. They NEVER wrote a sort!

So, I'd suggest looking into the system "sort" routine on whatever computer
you're using. I sure hope "Mr. Bill" (Gates, that is) thought of one.

Not EVERYTHING needs to be in Ada! (gasp!)

John Cupak

"Brien L. Christesen" <blchrist@rac2.wam.umd.edu> wrote in message
news:bg3fgg$qig$1@grapevine.wam.umd.edu...
>
>
> First off, I'm an Ada newbie, I've only been using it for about a month
> now.
>
> I am trying to sort ~1,000,000 (with potential to grow to 60 mil)
> records of 256 bytes each in Ada. The records are written to a binary
> file. Right now, I read in the file, and divide it into files greater
> than and less than a pivot value.  I then recursively call this division
> function until it reaches a set less than 100,000 records (if I make this
> number any larger I get a stack overflow on my windows box) it creates an
> array of the records, calls quicksort on it, and appends the result to a
> final results file.
>
> I couldn't really find much discussion of doing external sorts in Ada (or
> much literature on external sorts at all) so I'm not sure if this is a
> good approach to be taking, or if there is a better way to do the sort.  I
> tried creating an index, sorting the index, and then creating the results
> file based on the index.  Jumping around the file with direct_io led to
> awful results, though.  The execution time of the part of the code that
> read the index, got the corresponding value from the large record file,
> and wrote that record to a new file grew exponentially.
>
> Does anyone know of a good way to do this kind of sort?  Thanks in advance
> for any responses.