1 files changed, 13 insertions, 4 deletions
diff --git a/sort/sort_test.go b/sort/sort_test.go
index ee49893..4fd2a04 100644
--- a/sort/sort_test.go
+++ b/sort/sort_test.go
@@ -18,10 +18,19 @@ const maxSlowLength int = 100000
 type sortAlgorithm[V ds.Number] func(ds.ArrayList[V]) ds.ArrayList[V]
 
 func TestSleepSort(t *testing.T) {
-	a := ds.NewRandomArrayList[int](10, 10)
-	a = Sleep(a)
-	if !a.Sorted() {
-		t.Errorf("Array not sorted: %v", a)
+	orig := ds.NewRandomArrayList[int](10, 10)
+	in := make([]int, len(orig))
+	copy(in, orig)
+
+	out := Sleep(orig)
+	if !out.Sorted() {
+		t.Errorf("Array not sorted: %v", out)
+	}
+	// Also require the output to be a permutation of the input: sortedness alone
+	// would not catch a dropped or duplicated value. (Exhaustive termination /
+	// deadlock guarantees for the coordination live in formal/tla/SleepSort.tla.)
+	if !sameMultiset(in, out) {
+		t.Errorf("Sleep sort output is not a permutation of input: in=%v out=%v", in, out)
 	}
 }