Convert DS18B20 temperature to string
(Conversion) algorithms are a trade-off between size and speed. The fastest conversion is via a lookup table, but that takes a lot of code size, especially for 16-bit!  

This AVR application note shows methods for converting between binary and BCD for different word lengths. The application note is written for AVR assembly, but describes the algorithms in text and flowcharts, so it should be usable for other controllers as well.
You'll have to take the absolute value first, since the algorithms seem to be written for unsigned numbers.  

If you don't understand the algorithm completely,use the BCD as an intermediate step. The last step, from BCD to ASCII should be easy. Otherwise you can tweak the algorithm so that MSD and LSD are shifted to different bytes, so that you only have to OR with 0x30 to get the ASCII value.  

Since this was written for assembly it may be most code-efficient to write it in in-line assembly, instead of C.