1 files changed, 72 insertions, 23 deletions
diff --git a/libgo/go/sort/sort.go b/libgo/go/sort/sort.go
index ac8f4a661f..72d24efcea 100644
--- a/libgo/go/sort/sort.go
+++ b/libgo/go/sort/sort.go
@@ -2,12 +2,16 @@
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.
 
+//go:generate go run genzfunc.go
+
 // Package sort provides primitives for sorting slices and user-defined
 // collections.
 package sort
 
+import "reflect"
+
 // A type, typically a collection, that satisfies sort.Interface can be
-// sorted by the routines in this package.  The methods require that the
+// sorted by the routines in this package. The methods require that the
 // elements of the collection be enumerated by an integer index.
 type Interface interface {
 	// Len is the number of elements in the collection.
@@ -19,13 +23,6 @@ type Interface interface {
 	Swap(i, j int)
 }
 
-func min(a, b int) int {
-	if a < b {
-		return a
-	}
-	return b
-}
-
 // Insertion sort
 func insertionSort(data Interface, a, b int) {
 	for i := a + 1; i < b; i++ {
@@ -119,15 +116,15 @@ func doPivot(data Interface, lo, hi int) (midlo, midhi int) {
 	pivot := lo
 	a, c := lo+1, hi-1
 
-	for ; a != c && data.Less(a, pivot); a++ {
+	for ; a < c && data.Less(a, pivot); a++ {
 	}
 	b := a
 	for {
-		for ; b != c && !data.Less(pivot, b); b++ { // data[b] <= pivot
+		for ; b < c && !data.Less(pivot, b); b++ { // data[b] <= pivot
 		}
-		for ; b != c && data.Less(pivot, c-1); c-- { // data[c-1] > pivot
+		for ; b < c && data.Less(pivot, c-1); c-- { // data[c-1] > pivot
 		}
-		if b == c {
+		if b >= c {
 			break
 		}
 		// data[b] > pivot; data[c-1] <= pivot
@@ -167,11 +164,11 @@ func doPivot(data Interface, lo, hi int) (midlo, midhi int) {
 		//	data[a <= i < b] unexamined
 		//	data[b <= i < c] = pivot
 		for {
-			for ; a != b && !data.Less(b-1, pivot); b-- { // data[b] == pivot
+			for ; a < b && !data.Less(b-1, pivot); b-- { // data[b] == pivot
 			}
-			for ; a != b && data.Less(a, pivot); a++ { // data[a] < pivot
+			for ; a < b && data.Less(a, pivot); a++ { // data[a] < pivot
 			}
-			if a == b {
+			if a >= b {
 				break
 			}
 			// data[a] == pivot; data[b-1] < pivot
@@ -219,14 +216,63 @@ func quickSort(data Interface, a, b, maxDepth int) {
 // It makes one call to data.Len to determine n, and O(n*log(n)) calls to
 // data.Less and data.Swap. The sort is not guaranteed to be stable.
 func Sort(data Interface) {
-	// Switch to heapsort if depth of 2*ceil(lg(n+1)) is reached.
 	n := data.Len()
-	maxDepth := 0
+	quickSort(data, 0, n, maxDepth(n))
+}
+
+// maxDepth returns a threshold at which quicksort should switch
+// to heapsort. It returns 2*ceil(lg(n+1)).
+func maxDepth(n int) int {
+	var depth int
 	for i := n; i > 0; i >>= 1 {
-		maxDepth++
+		depth++
 	}
-	maxDepth *= 2
-	quickSort(data, 0, n, maxDepth)
+	return depth * 2
+}
+
+// lessSwap is a pair of Less and Swap function for use with the
+// auto-generated func-optimized variant of sort.go in
+// zfuncversion.go.
+type lessSwap struct {
+	Less func(i, j int) bool
+	Swap func(i, j int)
+}
+
+// Slice sorts the provided slice given the provided less function.
+//
+// The sort is not guaranteed to be stable. For a stable sort, use
+// SliceStable.
+//
+// The function panics if the provided interface is not a slice.
+func Slice(slice interface{}, less func(i, j int) bool) {
+	rv := reflect.ValueOf(slice)
+	swap := reflect.Swapper(slice)
+	length := rv.Len()
+	quickSort_func(lessSwap{less, swap}, 0, length, maxDepth(length))
+}
+
+// SliceStable sorts the provided slice given the provided less
+// function while keeping the original order of equal elements.
+//
+// The function panics if the provided interface is not a slice.
+func SliceStable(slice interface{}, less func(i, j int) bool) {
+	rv := reflect.ValueOf(slice)
+	swap := reflect.Swapper(slice)
+	stable_func(lessSwap{less, swap}, rv.Len())
+}
+
+// SliceIsSorted tests whether a slice is sorted.
+//
+// The function panics if the provided interface is not a slice.
+func SliceIsSorted(slice interface{}, less func(i, j int) bool) bool {
+	rv := reflect.ValueOf(slice)
+	n := rv.Len()
+	for i := n - 1; i > 0; i-- {
+		if less(i, i-1) {
+			return false
+		}
+	}
+	return true
 }
 
 type reverse struct {
@@ -315,7 +361,7 @@ func StringsAreSorted(a []string) bool { return IsSorted(StringSlice(a)) }
 
 // Notes on stable sorting:
 // The used algorithms are simple and provable correct on all input and use
-// only logarithmic additional stack space.  They perform well if compared
+// only logarithmic additional stack space. They perform well if compared
 // experimentally to other stable in-place sorting algorithms.
 //
 // Remarks on other algorithms evaluated:
@@ -335,7 +381,7 @@ func StringsAreSorted(a []string) bool { return IsSorted(StringSlice(a)) }
 //    unstable or rely on enough different elements in each step to encode the
 //    performed block rearrangements. See also "In-Place Merging Algorithms",
 //    Denham Coates-Evely, Department of Computer Science, Kings College,
-//    January 2004 and the reverences in there.
+//    January 2004 and the references in there.
 //  - Often "optimal" algorithms are optimal in the number of assignments
 //    but Interface has only Swap as operation.
 
@@ -344,7 +390,10 @@ func StringsAreSorted(a []string) bool { return IsSorted(StringSlice(a)) }
 // It makes one call to data.Len to determine n, O(n*log(n)) calls to
 // data.Less and O(n*log(n)*log(n)) calls to data.Swap.
 func Stable(data Interface) {
-	n := data.Len()
+	stable(data, data.Len())
+}
+
+func stable(data Interface, n int) {
 	blockSize := 20 // must be > 0
 	a, b := 0, blockSize
 	for b <= n {