Index: usr.bin/sort/coll.h
===================================================================
--- usr.bin/sort/coll.h
+++ usr.bin/sort/coll.h
@@ -64,6 +64,14 @@
 	int			 m;
 };
 
+/*
+ * Sort hint data for -R
+ */
+struct R_hint
+{
+	unsigned char		 cached[12];
+};
+
 /*
  * Status of a sort hint object
  */
@@ -83,6 +91,7 @@
 		struct n_hint		nh;
 		struct g_hint		gh;
 		struct M_hint		Mh;
+		struct R_hint		Rh;
 	}			v;
 };
 
Index: usr.bin/sort/coll.c
===================================================================
--- usr.bin/sort/coll.c
+++ usr.bin/sort/coll.c
@@ -981,6 +981,15 @@
 	return (numcoll_impl(kv1, kv2, offset, true));
 }
 
+/* Use hint space to memoize md5 computations, at least. */
+static void
+randomcoll_init_hint(struct key_value *kv, void *hash)
+{
+
+	memcpy(kv->hint->v.Rh.cached, hash, sizeof(kv->hint->v.Rh.cached));
+	kv->hint->status = HS_INITIALIZED;
+}
+
 /*
  * Implements random sort (-R).
  */
@@ -991,6 +1000,7 @@
 	struct bwstring *s1, *s2;
 	MD5_CTX ctx1, ctx2;
 	unsigned char hash1[MD5_DIGEST_LENGTH], hash2[MD5_DIGEST_LENGTH];
+	int cmp;
 
 	s1 = kv1->k;
 	s2 = kv2->k;
@@ -1003,6 +1013,14 @@
 	if (s1 == s2)
 		return (0);
 
+	if (kv1->hint->status == HS_INITIALIZED &&
+	    kv2->hint->status == HS_INITIALIZED) {
+		cmp = memcmp(kv1->hint->v.Rh.cached,
+		    kv2->hint->v.Rh.cached, sizeof(kv1->hint->v.Rh.cached));
+		if (cmp != 0)
+			return (cmp);
+	}
+
 	memcpy(&ctx1, &md5_ctx, sizeof(MD5_CTX));
 	memcpy(&ctx2, &md5_ctx, sizeof(MD5_CTX));
 
@@ -1012,6 +1030,11 @@
 	MD5Final(hash1, &ctx1);
 	MD5Final(hash2, &ctx2);
 
+	if (kv1->hint->status == HS_UNINITIALIZED)
+		randomcoll_init_hint(kv1, hash1);
+	if (kv2->hint->status == HS_UNINITIALIZED)
+		randomcoll_init_hint(kv2, hash2);
+
 	return (memcmp(hash1, hash2, sizeof(hash1)));
 }
 
Index: usr.bin/sort/sort.c
===================================================================
--- usr.bin/sort/sort.c
+++ usr.bin/sort/sort.c
@@ -583,6 +583,7 @@
 		break;
 	case 'R':
 		sm->Rflag = true;
+		need_hint = true;
 		need_random = true;
 		break;
 	case 'M':