does a beer with a high final gravity still need sugar added when bottling?

I wanted to make a strong batch, so I added a lot of extra sugar to the wart. I started with s.g. of 1.12, but I think it was even more case it was still pretty hot when I measured. After 16 days its at about 1.039. Its time to bottle, but do I still need to add sugar? I think there is still a lot of sugar in there .

Yes you still need to add priming sugar and should only bottle once the fermentation has completely finished.

Put it this way, if fermentation is not finished you'll never know how much of un-fermented sugars are in solution and how much CO2 (pressure) will yeast produce.
Result of that can be pretty messy..
But when you know that there is no un-fermented sugars you can calculate how much sugar you need to achieve desired volume of CO2 (depending on bottling volume and highest temperature of fermentation).

Wat was the recipe and how much yeast did you pitch? Has the gravity reading been stable for multiple days?

There are two things that might be going in here. Time is not a valid measure for when one should bottle your beer might still be fermenting and bottling now would lead to bombs. The second is that with a 1.12 SG your yeast might have given up (especially if you didn't pitch like 4 packets or a huge starter (like the leftover yeast cake from your last brew) and adding priming sugar and bottling will leave you with flat beer.

So the answer to the question you asked is yes you will need to add sugar when you bottle, the answer to the question that you didn't ask is no you probably should not bottle the beer now.