MathGroup Archive 2009

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: MergeSort with replacerepeated

  • To: mathgroup at
  • Subject: [mg100536] Re: MergeSort with replacerepeated
  • From: lshifr at
  • Date: Sun, 7 Jun 2009 05:01:32 -0400 (EDT)
  • References: <h0d6q8$som$>

Hi Luca,

you got me interested. Here is a result:

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

  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]};

  sort[lst_List] :=
    Map[h[#, h[]] &, lst] //. x_List :>
        {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,
      Infinity, h]];

The usage:


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,


On Jun 6, 12:45 am, Luca <w... at> 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