If r is not between i and j, there's no point in sorting...
Show that the expected running time is O(n).
