Re: MergeSort with replacerepeated

• To: mathgroup at smc.vnet.net
• Subject: [mg100536] Re: MergeSort with replacerepeated
• From: lshifr at gmail.com
• Date: Sun, 7 Jun 2009 05:01:32 -0400 (EDT)
• References: <h0d6q8\$som\$1@smc.vnet.net>

```Hi Luca,

you got me interested. Here is a result:

Clear[toLinkedList];
toLinkedList[x_List] := Fold[{#2, #1} &, {}, Reverse[x]];

Module[{h},
Clear[mergeLinked];
mergeLinked[x_h, y_h] :=
{x, y, h[]} //.
{{fst : h[hA_, tA_h], sec : h[hB_, tB_h], e_h} :>
If[hA > hB, {tA, sec, h[hA, e]}, {fst, tB, h[hB, e]}],
{fst : h[hA_, _h], h[], e_h} :> h[hA, e],
{h[], sec : h[hB_, _h], e_h} :> h[hB, e]};

Clear[sort];
sort[lst_List] :=
Flatten[
Map[h[#, h[]] &, lst] //. x_List :>
Flatten[
{toLinkedList@x, {}} //. {{hd1_, {hd2_, tail_List}},
accum_List} :> {tail, {accum,
Last[h[mergeLinked[hd1, hd2], h[]] //.
h[h[hd_, tl_h], acc_h] :> h[tl, h[hd,
acc]]]}}],
Infinity, h]];

The usage:

sort[yourlist]

This is a linked list - based implementation that will give you an
expected log-linear performance of mergesort and has a lot of
ReplaceRepeated in it:). I think it is a good case to show that
ReplaceRepeated *can* be used  efficiently. In this case, this is
achieved by using linked lists and organizing results so that the very
first attempt of the pattern-matcher is always a match, so it does not
waste time on false matching attempts (this is a main source of
inefficiency of straightforwardly written code involving
ReplaceRepeated). Merging already sorted lists is done by transforming
them into linked lists with a head <h>, while collecting sublists
pairwise to merge each pair is done by transforming the list of
already merged sublists into a linked list with a "normal" head List.
The last (most internal) ReplaceRepeated is used to reverse the merged
sub-list (well, not really list - linked list with a head <h>) since
<mergeLinked> does not produce it in the right order to use in the
next iterations.  Of course, this is (in this case at least) an
academic exercise,  since the built-in Sort is vastly faster. Anyway,
enjoy!

Regards,
Leonid

On Jun 6, 12:45 am, Luca <w... at lucabedogni.it> wrote:
> Hi
>    I have to write a mathematica function, using replace repeated, th=
at realizes mergesort.
>
> I've already written the mergesort function, but not with replace repeate=
d. Any hint on that?
>
> Thank you

```

• Prev by Date: Re: Re: RandomReal gets stuck
• Next by Date: Re: MergeSort with replacerepeated - a follow-up
• Previous by thread: Re: Re: interfacing odd usb device to mathematica
• Next by thread: mergeSort with ReplaceRepeated