diff options
author | Stefan Nilsson <snilsson@nada.kth.se> | 2012-03-22 09:27:02 -0700 |
---|---|---|
committer | Robert Griesemer <gri@golang.org> | 2012-03-22 09:27:02 -0700 |
commit | 08959defa89f3a37775f744a52bfbbff93e742d6 (patch) | |
tree | 5ea4445d397ed06b147f499850e0a4849bad3f9c | |
parent | 2795a15c0c460fac9a760557a8c18d79a857faab (diff) | |
download | go-08959defa89f3a37775f744a52bfbbff93e742d6.tar.gz go-08959defa89f3a37775f744a52bfbbff93e742d6.zip |
sort: add time complexity to doc
Let's tell the world that Go's sort is O(n log n).
Surely this is a feature we intend to keep.
R=golang-dev, gri
CC=golang-dev
https://golang.org/cl/5867045
-rw-r--r-- | src/pkg/sort/sort.go | 3 |
1 files changed, 2 insertions, 1 deletions
diff --git a/src/pkg/sort/sort.go b/src/pkg/sort/sort.go index ca715645af..62a4d55e79 100644 --- a/src/pkg/sort/sort.go +++ b/src/pkg/sort/sort.go @@ -184,7 +184,8 @@ func quickSort(data Interface, a, b, maxDepth int) { } // Sort sorts data. -// The algorithm used is not guaranteed to be a stable sort. +// 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() |