Rather than explicitly construct a record array, couldn't one just use the one `Table` has built-in? Eg., from a quick test, both the following seem to work:
```
out_keys = np.sort(table._data[list(keys)], order=keys)

out_keys = np.sort(table[tuple(keys)]._data, order=keys)
```
Here, the first should be by far the fastest. (Note that one does need the `list(keys)` to allow multiple columns to be gotten out of the recarray (and `tuple(keys)` to ensure the table stays a table rather than become a column for a single key).