diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/sort/sort.go | 22 |
1 files changed, 14 insertions, 8 deletions
diff --git a/src/sort/sort.go b/src/sort/sort.go index 63f8894a19..55134956c0 100644 --- a/src/sort/sort.go +++ b/src/sort/sort.go @@ -316,7 +316,7 @@ func StringsAreSorted(a []string) bool { return IsSorted(StringSlice(a)) } // data.Less and O(n*log(n)*log(n)) calls to data.Swap. func Stable(data Interface) { n := data.Len() - blockSize := 20 + blockSize := 20 // must be > 0 a, b := 0, blockSize for b <= n { insertionSort(data, a, b) @@ -332,7 +332,9 @@ func Stable(data Interface) { a = b b += 2 * blockSize } - symMerge(data, a, a+blockSize, n) + if m := a + blockSize; m < n { + symMerge(data, a, m, n) + } blockSize *= 2 } } @@ -352,11 +354,11 @@ func Stable(data Interface) { // rotation algorithm which uses O(M+N+gcd(M+N)) assignments. The argumentation // in the paper carries through for Swap operations, especially as the block // swapping rotate uses only O(M+N) Swaps. +// +// symMerge assumes non-degenerate arguments: a < m && m < b. +// Having the caller check this condition eliminates many leaf recursion calls, +// which improves performance. func symMerge(data Interface, a, m, b int) { - if a >= m || m >= b { - return - } - mid := a + (b-a)/2 n := mid + m var start, r int @@ -380,8 +382,12 @@ func symMerge(data Interface, a, m, b int) { end := n - start rotate(data, start, m, end) - symMerge(data, a, start, mid) - symMerge(data, mid, end, b) + if a < start && start < mid { + symMerge(data, a, start, mid) + } + if mid < end && end < b { + symMerge(data, mid, end, b) + } } // Rotate two consecutives blocks u = data[a:m] and v = data[m:b] in data: |