The Merge Algorithm

Assume we are merging lists A and B into list C.

Ax := 1; Bx := 1; Cx := 1;

while Ax ? n and Bx ? n do

if A[Ax] < B[Bx] then

C[Cx] := A[Ax];

Ax := Ax + 1;

else

C[Cx] := B[Bx];

Bx := Bx + 1;

endif

Cx := Cx + 1;

endwhile

while Ax ? n do

C[Cx] := A[Ax];

Ax := Ax + 1;

Cx := Cx + 1;

endwhile

while Bx ? n do

C[Cx] := B[Bx];

Bx := Bx + 1;

Cx := Cx + 1;

endwhile

Previous slide

Next slide

Back to first slide

View graphic version