sort: optimize symMerge performance for blocks with one element

Use direct binary insertion instead of recursive calls to symMerge
when one of the blocks has only one element.

benchmark                   old ns/op      new ns/op      delta
BenchmarkStableString1K     421999         397629         -5.77%
BenchmarkStableInt1K        123422         120592         -2.29%
BenchmarkStableInt64K       9629094        9620200        -0.09%
BenchmarkStable1e2          123089         120209         -2.34%
BenchmarkStable1e4          39505228       36870029       -6.67%
BenchmarkStable1e6          8196612367     7630840157     -6.90%

Change-Id: I49905a909e8595cfa05920ccf9aa00a8f3036110
Reviewed-on: https://go-review.googlesource.com/2219
Reviewed-by: Robert Griesemer <gri@golang.org>

1 files changed, 48 insertions, 0 deletions

diff --git a/src/sort/sort.go b/src/sort/sort.go
index 600a486a0e..4ca027b614 100644
--- a/src/sort/sort.go
+++ b/src/sort/sort.go
@@ -359,6 +359,54 @@ func Stable(data Interface) {
 // Having the caller check this condition eliminates many leaf recursion calls,
 // which improves performance.
 func symMerge(data Interface, a, m, b int) {
+	// Avoid unnecessary recursions of symMerge
+	// by direct insertion of data[a] into data[m:b]
+	// if data[a:m] only contains one element.
+	if m-a == 1 {
+		// Use binary search to find the lowest index i
+		// such that data[i] >= data[a] for m <= i < b.
+		// Exit the search loop with i == b in case no such index exists.
+		i := m
+		j := b
+		for i < j {
+			h := i + (j-i)/2
+			if data.Less(h, a) {
+				i = h + 1
+			} else {
+				j = h
+			}
+		}
+		// Swap values until data[a] reaches the position before i.
+		for k := a; k < i-1; k++ {
+			data.Swap(k, k+1)
+		}
+		return
+	}
+
+	// Avoid unnecessary recursions of symMerge
+	// by direct insertion of data[m] into data[a:m]
+	// if data[m:b] only contains one element.
+	if b-m == 1 {
+		// Use binary search to find the lowest index i
+		// such that data[i] > data[m] for a <= i < m.
+		// Exit the search loop with i == m in case no such index exists.
+		i := a
+		j := m
+		for i < j {
+			h := i + (j-i)/2
+			if !data.Less(m, h) {
+				i = h + 1
+			} else {
+				j = h
+			}
+		}
+		// Swap values until data[m] reaches the position i.
+		for k := m; k > i; k-- {
+			data.Swap(k, k-1)
+		}
+		return
+	}
+
 	mid := a + (b-a)/2
 	n := mid + m
 	var start, r int