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