function merge( a, b : tree ) : tree;
	var	bota, botb, r, temp : tree;

	begin
	if a=nil then merge := b
	else if b=nil then merge := a
	else	begin
		{*** find bottom of a's rightmost edge ***}
		bota := a^.right;	a^.right := nil;
		{*** bottom of b's leftmost edge ***}
		botb := b^.left;	b^.left := nil;
		r := nil;
		{*** merging loop ***}
		while (bota<>nil) and (botb<>nil) do
			if bota^.k < botb^.k then begin
				temp := bota^.right;
				if r=nil then	bota^.right := bota
					else	begin
						bota^.right := r^.right;
						r^.right := bota
						end;
				r := bota;
				bota := temp
				end
			else	begin
				temp := botb^.left;
				if r=nil then	botb^.left := botb
					else	begin
						botb^.left := r^.left;
						r^.left := botb
						end;
				r := botb;
				botb := temp
				end;
		{*** one edge is exhausted, finish merge ***}
		if botb=nil then begin
			a^.right := r^.right;
			r^.right := bota;
			merge := a
			end
		else	begin
			b^.left := r^.left;
			r^.left := botb;
			merge := b
			end
		end
	end;