External "bucket" sort
It is not necessary to decode and encode UTF-8, as split('\t') and lstrip('.\\') work fine on UTF-8-encoded strings. 
The programs keeps an unlimited number of temporary files open simultaneously and will fail after exceeding the platform's maximum for open files. An approach where only a certain number of most recently used files are kept open could be appropriate here.
file_o.write(temp_files[key].read()) reads the entire file in memory. To conserve memory, use a loop and give a block size argument to read.