1 files changed, 62 insertions, 6 deletions

diff --git a/libgo/go/sort/sort_test.go b/libgo/go/sort/sort_test.go
index 5007a92a562..a5640151cb2 100644
--- a/libgo/go/sort/sort_test.go
+++ b/libgo/go/sort/sort_test.go
@@ -169,6 +169,13 @@ func (d *testingData) Swap(i, j int) {
 	d.data[i], d.data[j] = d.data[j], d.data[i]
 }
 
+func min(a, b int) int {
+	if a < b {
+		return a
+	}
+	return b
+}
+
 func lg(n int) int {
 	i := 0
 	for 1<<uint(i) < n {
@@ -177,7 +184,7 @@ func lg(n int) int {
 	return i
 }
 
-func TestBentleyMcIlroy(t *testing.T) {
+func testBentleyMcIlroy(t *testing.T, sort func(Interface)) {
 	sizes := []int{100, 1023, 1024, 1025}
 	if testing.Short() {
 		sizes = []int{100, 127, 128, 129}
@@ -253,7 +260,7 @@ func TestBentleyMcIlroy(t *testing.T) {
 
 					desc := fmt.Sprintf("n=%d m=%d dist=%s mode=%s", n, m, dists[dist], modes[mode])
 					d := &testingData{desc, t, mdata[0:n], n * lg(n) * 12 / 10, 0}
-					Sort(d)
+					sort(d)
 
 					// If we were testing C qsort, we'd have to make a copy
 					// of the slice and sort it ourselves and then compare
@@ -274,9 +281,58 @@ func TestBentleyMcIlroy(t *testing.T) {
 	}
 }
 
-func min(a, b int) int {
-	if a < b {
-		return a
+func TestSortBM(t *testing.T) {
+	testBentleyMcIlroy(t, Sort)
+}
+
+func TestHeapsortBM(t *testing.T) {
+	testBentleyMcIlroy(t, Heapsort)
+}
+
+// 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
+}
+
+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)
+			}
+		}
 	}
-	return b
+
+	if _, present := d.keys[i]; !present {
+		d.candidate = i
+		return false
+	}
+	if _, present := d.keys[j]; !present {
+		d.candidate = j
+		return true
+	}
+
+	return d.keys[i] >= d.keys[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
+	data := make([]int, size)
+	for i := 0; i < size; i++ {
+		data[i] = i
+	}
+
+	d := &adversaryTestingData{data, make(map[int]int), 0}
+	Sort(d) // This should degenerate to heapsort.
 }