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:

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

Module[{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,
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
pairwise to merge each pair is done by transforming the list of
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