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 in two pieces for a while. We can move the endpoints of the lefthand piece to 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 moving 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 moving 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.