Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer

bitingduck's scratchpad

by bitingduck (Chaplain)
on May 19, 2012 at 01:38 UTC ( #971379=scratchpad: print w/replies, xml ) Need Help??

compare leftmost unmerged element in first series foreach(leftmost unmerged element) if(S1[1]>=S2[1]){ # where index 1 is leftmost swap(S2[1],B[1]) } else { swap(S1[1],B[1]) } 2a looks like H2H3I1I2J1 A1A2A3B4B5 B1B2B3D1D2 C1C2E3G2G3 E1E2F1G1H1 --buf----- ----------S1--------- ----S2---- ---Block5- we apply the comparison A1>C1? A1 is smaller, so swap A1 with H2: keep track of buffer element locations (it's going to migrate and be i +n two pieces for a while. We can move the endpoints of the lefthand piece t +o after the merge and keep track of the pointer in S2 for buffer pieces on the lefthand +end. here it is after the first swap (M is the merge): A1 H3I1I2J1H2 A2A3B4B5 B1B2B3D1D2 C1C2E3G2G3 E1E2F1G1H1 M- buf------- -------S1--------- ----S2---- ---Block5-- next step, A2>C1? no, swap A2 into Buffer, move pointers A1 A2I1I2J1H2 H3A3B4B5 B1B2B3D1D2 C1C2E3G2G3 E1E2F1G1H1 #before movi +ng pointers M- -----Buf-- --------S1--------- ----S2---- ---Block5- A1A2 I1I2J1H2H3 A3B4B5 B1B2B3D1D2 C1C2E3G2G3 E1E2F1G1H1 #after moving + pointers M--- ---Buf---- ------S1--------- ----S2---- ---Block5- A3>C1? A1A2A3 I2I1H2H3J1 B4B5 B1B2B3D1D2 C1C2E3G2G3 E1E2F1G1H1 #after moving + pointers M----- -Buf------ ----S1--------- ----S2---- ---Block5- eventually it's going to look like 2b, with the buffer split into part + of S1. --B--- -B-- A1A2A3B4B5B1B2B3C1C2 H2H3I1 D1D2 I2J1 E3G2G3 E1E2F1G1H1 #after mo +ving pointers M------------------- (S1B)^ -S1- (S2B)^ S2---- ---Block5- It's probably easiest to track how far into S1 and S2 the two buffers +have gone, and use B' and B'' as two relative pointers to separate the unmerged parts + of S1 and S2 from from the buffer elements that are migrating in.
Log In?

What's my password?
Create A New User
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (5)
As of 2016-12-03 21:49 GMT
Find Nodes?
    Voting Booth?
    On a regular basis, I'm most likely to spy upon:

    Results (60 votes). Check out past polls.