I think the intention is that the job will relate to the running time of other algorithms and that sorting things is a toy problem you can use to test whether they know anything about that subject in general.

There may be better ways to assess that, though. For example, you could ask them to give one or two examples each of algorithms that are O(1), O(log N), O(N), O(N log N), and O(N^2), and O(something worse than N^2).