Это by design; опция -R не совсем сортирует в случайном порядке, она берёт случайную хэш функцию, применяет её к каждой строке и потом сортирует их по полученным хэшам, т.о. выглядит это очень похоже на случайное перемешивание, но это не совсем так.

Тогда в ман странице нужно написать правду. Так как лично я фразу "sort by random hash of keys" понял как "сортировка по случайному хэшу от ключа". Из описания не понятно, применяется ли одинаковая процедура хэширования ко всем ключам или нет.

sort(1) manpage выглядит лаконичной версией info sort, в котором написано:
"Sort by hashing the input keys and then sorting the hash values. Choose the hash function at random, ensuring that it is free of collisions so that differing keys have differing hash values. This is like a random permutation of the inputs, except that keys with the same value sort together."

(В ответ на комментарий №3)
> sort(1) manpage выглядит лаконичной версией info sort, в котором написано:
> "Sort by hashing the input keys and then sorting the hash values. Choose the
> hash function at random, ensuring that it is free of collisions so that
> differing keys have differing hash values. This is like a random permutation of
> the inputs, except that keys with the same value sort together."

Тогда вопросов не имею. Сам виноват.