sort: fix TestAdversary

There are some major problems with TestAdversary (based on "A Killer
Adversary for Quicksort"[1] by M. D. McIlroy). See #21581 for details.

Rewrite the test to closely match the version in the paper so it can
be verified as correct by virtue of similarity.

The only major difference between this new version and the version in
the paper is that this version swaps the values directly instead of
permuting an array of indices because we don't need to recover the
original permutation.

This new version also counts the number of calls to Less() and fails
the test if there are too many.

Fixes #21581.

[1]: http://www.cs.dartmouth.edu/~doug/mdmspe.pdf

Change-Id: Ia94b5b6d288b8fa3805a5fa27661cebbc5bad9a7
Reviewed-on: https://go-review.googlesource.com/58330
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>

1 files changed, 40 insertions, 20 deletions

diff --git a/src/sort/sort_test.go b/src/sort/sort_test.go
index 45713a28cc..092135e588 100644
--- a/src/sort/sort_test.go
+++ b/src/sort/sort_test.go
@@ -458,49 +458,69 @@ func TestStableBM(t *testing.T) {
 // This is based on the "antiquicksort" implementation by M. Douglas McIlroy.
 // See http://www.cs.dartmouth.edu/~doug/mdmspe.pdf for more info.
 type adversaryTestingData struct {
-	data      []int
-	keys      map[int]int
-	candidate int
+	t         *testing.T
+	data      []int // item values, initialized to special gas value and changed by Less
+	maxcmp    int   // number of comparisons allowed
+	ncmp      int   // number of comparisons (calls to Less)
+	nsolid    int   // number of elements that have been set to non-gas values
+	candidate int   // guess at current pivot
+	gas       int   // special value for unset elements, higher than everything else
 }
 
 func (d *adversaryTestingData) Len() int { return len(d.data) }
 
 func (d *adversaryTestingData) Less(i, j int) bool {
-	if _, present := d.keys[i]; !present {
-		if _, present := d.keys[j]; !present {
-			if i == d.candidate {
-				d.keys[i] = len(d.keys)
-			} else {
-				d.keys[j] = len(d.keys)
-			}
+	if d.ncmp >= d.maxcmp {
+		d.t.Fatalf("used %d comparisons sorting adversary data with size %d", d.ncmp, len(d.data))
+	}
+	d.ncmp++
+
+	if d.data[i] == d.gas && d.data[j] == d.gas {
+		if i == d.candidate {
+			// freeze i
+			d.data[i] = d.nsolid
+			d.nsolid++
+		} else {
+			// freeze j
+			d.data[j] = d.nsolid
+			d.nsolid++
 		}
 	}
 
-	if _, present := d.keys[i]; !present {
+	if d.data[i] == d.gas {
 		d.candidate = i
-		return false
-	}
-	if _, present := d.keys[j]; !present {
+	} else if d.data[j] == d.gas {
 		d.candidate = j
-		return true
 	}
 
-	return d.keys[i] >= d.keys[j]
+	return d.data[i] < d.data[j]
 }
 
 func (d *adversaryTestingData) Swap(i, j int) {
 	d.data[i], d.data[j] = d.data[j], d.data[i]
 }
 
-func TestAdversary(t *testing.T) {
-	const size = 100
+func newAdversaryTestingData(t *testing.T, size int, maxcmp int) *adversaryTestingData {
+	gas := size - 1
 	data := make([]int, size)
 	for i := 0; i < size; i++ {
-		data[i] = i
+		data[i] = gas
 	}
+	return &adversaryTestingData{t: t, data: data, maxcmp: maxcmp, gas: gas}
+}
 
-	d := &adversaryTestingData{data, make(map[int]int), 0}
+func TestAdversary(t *testing.T) {
+	const size = 10000            // large enough to distinguish between O(n^2) and O(n*log(n))
+	maxcmp := size * lg(size) * 4 // the factor 4 was found by trial and error
+	d := newAdversaryTestingData(t, size, maxcmp)
 	Sort(d) // This should degenerate to heapsort.
+	// Check data is fully populated and sorted.
+	for i, v := range d.data {
+		if v != i {
+			t.Errorf("adversary data not fully sorted")
+			t.FailNow()
+		}
+	}
 }
 
 func TestStableInts(t *testing.T) {