Re: MergeSort with replacerepeated - a follow-up

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

Luca, 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): Clear[toLinkedList]; toLinkedList[x_List] := Fold[{#2, #1} &, {}, Reverse[x]]; Module[{h}, Clear[mergeLinked]; 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]}}]; 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] ];(* 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). 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