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