About the end of your post:You cannot both read and write in a same file; your "two-step solution" is OK. I did not know it was OK to redirect twice the standard input; to avoid touching the disk I would have created named pipes, as in this short (untested) script:
mkfifo file1.sorted file2.sorted sort -k 1b,1 -o file1.sorted file1 & sort -k 1b,1 -o file2.sorted file2 & join file1.sorted file2.sorted > Joined-file0102.txt