Is there a way to sort by taxonomy?
There's no way to do it with the default content admin page, short of writing code to alter the form. Vocabularies aren't linked exclusively to nodes in Drupal 7, they can be linked to any type of entity using the field system, so having this functionality wouldn't make sense by default any more.

Creating a View is definitely the right way to go; personally I'd install the Administration Views module which replaces (amongst others) the default content admin page with a View. 

The module page says it provides support for filtering by vocabulary out of the box, but even if it doesn't provide sorting you could easily just tweak the View to your own requirements.