Looking at your image, because its a sky scene, I would recommend that you use the clone brush tool and selections of different areas of the sky and the eraser tool(low hardness setting).
The gradient tool is much too regular for a cloudy sky scene. So dicard the mask(right click mask, Layers palette, discard Layer mask).
The other way will be much more irregular, thus making the join harder(impossible?) to detect.
sent you back a vquick edit, enough for you to get the idea.
Moe: It could have been a real ugly situation, but luckily I managed to shoot him in the spine.