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.
|