diff options
author | Stefan Nilsson <snilsson@nada.kth.se> | 2010-12-02 09:18:20 -0800 |
---|---|---|
committer | Robert Griesemer <gri@golang.org> | 2010-12-02 09:18:20 -0800 |
commit | 6f1835dce02b592b28a4ea9bb9a77dbc990198a2 (patch) | |
tree | 93bac2684ce8884074d290be0e53b43c85adf0d1 | |
parent | 4e40a03682aca2f0283689b21f9dc5b2919fc464 (diff) | |
download | go-6f1835dce02b592b28a4ea9bb9a77dbc990198a2.tar.gz go-6f1835dce02b592b28a4ea9bb9a77dbc990198a2.zip |
Sort: reduced stack depth to lg(n) in quickSort
Doing the tail recursion elimination explicitly
seems safer than leaving it to the compiler;
the code is still clean and easy to understand.
R=r, r2, gri
CC=golang-dev
https://golang.org/cl/3373041
-rw-r--r-- | src/pkg/sort/sort.go | 16 |
1 files changed, 12 insertions, 4 deletions
diff --git a/src/pkg/sort/sort.go b/src/pkg/sort/sort.go index 2abe22d5c7..02e647fca9 100644 --- a/src/pkg/sort/sort.go +++ b/src/pkg/sort/sort.go @@ -122,11 +122,19 @@ func doPivot(data Interface, lo, hi int) (midlo, midhi int) { } func quickSort(data Interface, a, b int) { - if b-a > 7 { + for b-a > 7 { mlo, mhi := doPivot(data, a, b) - quickSort(data, a, mlo) - quickSort(data, mhi, b) - } else if b-a > 1 { + // Avoiding recursion on the larger subproblem guarantees + // a stack depth of at most lg(b-a). + if mlo-a < b-mhi { + quickSort(data, a, mlo) + a = mhi // i.e., quickSort(data, mhi, b) + } else { + quickSort(data, mhi, b) + b = mlo // i.e., quickSort(data, a, mlo) + } + } + if b-a > 1 { insertionSort(data, a, b) } } |