Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!samsung!munnari.oz.au!goanna!ok
From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe)
Newsgroups: comp.lang.misc
Subject: Re: Sorting
Message-ID: <4373@goanna.cs.rmit.oz.au>
Date: 26 Nov 90 09:41:46 GMT
References: <11628@alice.att.com>
Organization: Comp Sci, RMIT, Melbourne, Australia
Lines: 30

In article <11628@alice.att.com>, dmr@alice.att.com (Dennis Ritchie) writes:
> But I do have a serious question.  I've got a boxcar with 10,000 8-mm tapes,
> each containing 10,000,000 100-byte binary records
> without any substructure.  I need to get these records sorted.
> Can someone quote me a cost and expected delivery time?

This is a very interesting question, because the answer isn't entirely
a computer science one.  This is clearly outside the scope of internal
sorting.  I'd go straight to Knuth V3, and of course to the specs of the
8-mm tape drives.  However, the absolute *minimum* is obviously that each
tape must be located, put in a drive, removed from the drive, and restored
to its place.  Say 5--10 minutes of handling time.  We're talking about an
absolute minimum of somewhere around 25 man-weeks of "operator" time just
to read each record once.  The cost is thus going to depend on the cost of
labour.  For the 100-boxcar version, it might even be worth building
special tape-handling machinery.

> Since I understand that this will run into big bucks, I trust
> your company can give a brief account of its technical approach
> before I write the purchase orders.

How will "trade secret" do (:-)?  Non-"technical" factors such as
"we're going to ship it to the Far East" might easily dominate
technical ones for a problem this size.  I trust that any company
approached for real with this problem would start by saying "why
do you need to have these things sorted; can we help you change your
set-up so they're generated in the right order; ...".   The fastest
way to do anything is after all to ensure that it doesn't _need_ doing.
-- 
I am not now and never have been a member of Mensa.		-- Ariadne.