From c5488d4f004e9f38e5fb996dd709a73aed03cd00 Mon Sep 17 00:00:00 2001 From: Stefan Nilsson Date: Tue, 20 Mar 2012 14:23:12 -0700 Subject: [PATCH] sort: fix computation of maxDepth to avoid infinite loop The current computation loops indefinitely if n > 1<<30 (for 32-bit ints). R=golang-dev, gri CC=golang-dev https://golang.org/cl/5848067 --- src/pkg/sort/sort.go | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/src/pkg/sort/sort.go b/src/pkg/sort/sort.go index 60f2d9ab40..ca715645af 100644 --- a/src/pkg/sort/sort.go +++ b/src/pkg/sort/sort.go @@ -186,10 +186,10 @@ func quickSort(data Interface, a, b, maxDepth int) { // Sort sorts data. // The algorithm used is not guaranteed to be a stable sort. func Sort(data Interface) { - // Switch to heapsort if depth of 2*ceil(lg(n)) is reached. + // Switch to heapsort if depth of 2*ceil(lg(n+1)) is reached. n := data.Len() maxDepth := 0 - for 1< 0; i >>= 1 { maxDepth++ } maxDepth *= 2 -- 2.50.0