MathGroup Archive 2009

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

Search the Archive

Re: MergeSort with replacerepeated - a follow-up

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


I just found a bug in my previous version of <mergeLinked> - I tried
to take a short-cut and that was a wrong move. Here is the correct
code (changes in the last 2 rules for mergeLinked, plus extra Last):

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

  mergeLinked[x_h, y_h] :=
   Last[{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_, tA_h], h[], e_h} :> {tA, h[], h[hA, e]},
      {h[], sec : h[hB_, tB_h], e_h} :> {h[], tB, h[hB, e]}}];

  sort[lst_List] :=
    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]
];(* Module *)

Now it should work correctly (but somewhat slower than the wrong
version alas :). Sorry for the confusion. Also, let me add that the
present implementation will not work correctly if the elements of the
list to be sorted are composite expressions themselves involving
lists. This can be easily fixed if needed, by replacing some lists in
<sort> with another head like <h>, and modifying the internal Flatten
appropriately (but in this case you will probably need as well to use
a different comparison function in mergeLinked).


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: MergeSort with replacerepeated
  • Next by Date: Re: Possible bug in Eigenvalues[ ] ???
  • Previous by thread: Re: Re: Re: mergeSort with ReplaceRepeated
  • Next by thread: Re: Why is recursion so slow in Mathematica?