Hi!

Is it possible to implement a merge-sort in Pascal without having 
dynamic arrays and without having to use pointers (Linked lists / linear 
lists)?
Google only brought up results using pointers...

Thank you!

regards,
    Chriss

On Thu, 22 Apr 2004 18:11:50 +0200, Christian Muenscher <crion@gmx.de>
wrote:

>Is it possible to implement a merge-sort in Pascal without having 
>dynamic arrays and without having to use pointers (Linked lists / linear 
>lists)?
>Google only brought up results using pointers...

Yes, if you can make static arrays large enough for the data.

---
Replace you know what by j to email

On 2004-04-22, Christian Muenscher <crion@gmx.de> wrote:
> Hi!
>
> Is it possible to implement a merge-sort in Pascal without having 
> dynamic arrays and without having to use pointers (Linked lists / linear 
> lists)?
> Google only brought up results using pointers...

Only if the number of files is limited.

Without dynamic mem there is no way to keep track of a variable number of
files.

It also depends on what you call merge sort. Is it only the last stage, or 
does it involve the creation of the sorted beginfiles also?

"Christian Muenscher" <crion@gmx.de> wrote in message news:c68qri$9cchh$1@ID-5299.news.uni-berlin.de...
> Hi!
>
> Is it possible to implement a merge-sort in Pascal without having
> dynamic arrays and without having to use pointers (Linked lists / linear
> lists)?
> Google only brought up results using pointers...
>
> Thank you!
>
> regards,
>     Chriss

Whats wrong with pointers ?

Anyways, no, ISO 7185 Pascal (the original Pascal) would need
either an array larger than the anticipated data, or pointers.
That (pointers) can be made much more space efficent by allocating
data in "chunks" of 100 or so data items, instead of one data, one
pointer.

In any case, variable length arrays is a common Pascal extention.
Your compiler may offer such a feature.

Scott Moore wrote:
> "Christian Muenscher" <crion@gmx.de> wrote in message
>>
>> Is it possible to implement a merge-sort in Pascal without
>> having dynamic arrays and without having to use pointers (Linked
>> lists / linear lists)?
>> Google only brought up results using pointers...
> 
> Whats wrong with pointers ?
> 
> Anyways, no, ISO 7185 Pascal (the original Pascal) would need
> either an array larger than the anticipated data, or pointers.
> That (pointers) can be made much more space efficent by allocating
> data in "chunks" of 100 or so data items, instead of one data, one
> pointer.
> 
> In any case, variable length arrays is a common Pascal extention.
> Your compiler may offer such a feature.

There are various flavors of merge sorts.  One operates in memory,
preferably on linked lists (which in turn can be implemented in
arrays).  Another merges external files, and is basically
unlimited as to final file size.  One extreme of this is
poly-phase sort.

-- 
Chuck F (cbfalconer@yahoo.com) (cbfalconer@worldnet.att.net)
   Available for consulting/temporary embedded and systems.
   <http://cbfalconer.home.att.net>  USE worldnet address!

I was about to say that myself!  About 15 years ago, I wrote a very
primitive spell-checker (hmm -- maybe 20 years ago!) that broke a
manuscript apart into words, sorted the words, then compared them with
a (sorted) dictionary.  As I was using a PDP-11 with (I think) at most
2M memory (my memory is starting to go here), I definitely needed an
"external sort" and coded a version of polyphase merge sort, following
the example in Wirth's book "Algorithms + Data Structures = Programs".
Definitely "vanilla Pascal", no dynamic arrays, and no pointers in
this particular program.

Bob Schor
Pascal Enthusiast

On Fri, 23 Apr 2004 09:53:41 GMT, CBFalconer <cbfalconer@yahoo.com>
wrote:

>Scott Moore wrote:
>> "Christian Muenscher" <crion@gmx.de> wrote in message
>>>
>>> Is it possible to implement a merge-sort in Pascal without
>>> having dynamic arrays and without having to use pointers (Linked
>>> lists / linear lists)?
>>> Google only brought up results using pointers...
>> 
>> Whats wrong with pointers ?
>> 
>> Anyways, no, ISO 7185 Pascal (the original Pascal) would need
>> either an array larger than the anticipated data, or pointers.
>> That (pointers) can be made much more space efficent by allocating
>> data in "chunks" of 100 or so data items, instead of one data, one
>> pointer.
>> 
>> In any case, variable length arrays is a common Pascal extention.
>> Your compiler may offer such a feature.
>
>There are various flavors of merge sorts.  One operates in memory,
>preferably on linked lists (which in turn can be implemented in
>arrays).  Another merges external files, and is basically
>unlimited as to final file size.  One extreme of this is
>poly-phase sort.