Order by where conditions
Use a subquery, something like:

SELECT * FROM (
  SELECT
    t.*,
    key REGEXP 'some long regular expression' AS a,
    key REGEXP 'some other long regular expression' AS b
  FROM table t
  WHERE a OR b
)
ORDER BY a DESC, b DESC;