MySQL sorting by 3 columns or UNION them

Doesn't this give you what you want?

http://sqlfiddle.com/#!2/b2a858/26

Just sort by not_existing first?

What's the problem here? You have your sort but with not_existing records at the end - these are also sorted in the same way