Beefy Boxes and Bandwidth Generously Provided by pair Networks
more useful options

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 pondering the Monastery: (4)
As of 2017-08-19 23:13 GMT
Find Nodes?
    Voting Booth?
    Who is your favorite scientist and why?

    Results (312 votes). Check out past polls.