Update Go library to last weekly.

[pf3gnuchains/gcc-fork.git] / libgo / go / sort / sort.go

diff --git a/libgo/go/sort/sort.go b/libgo/go/sort/sort.go
index 0a4a437..83ee170 100644 (file)
--- a/libgo/go/sort/sort.go
+++ b/libgo/go/sort/sort.go
@@ -37,10 +37,47 @@ func insertionSort(data Interface, a, b int) {
        }
 }
 
+// siftDown implements the heap property on data[lo, hi).
+// first is an offset into the array where the root of the heap lies.
+func siftDown(data Interface, lo, hi, first int) {
+       root := lo
+       for {
+               child := 2*root + 1
+               if child >= hi {
+                       break
+               }
+               if child+1 < hi && data.Less(first+child, first+child+1) {
+                       child++
+               }
+               if !data.Less(first+root, first+child) {
+                       return
+               }
+               data.Swap(first+root, first+child)
+               root = child
+       }
+}
+
+func heapSort(data Interface, a, b int) {
+       first := a
+       lo := 0
+       hi := b - a
+
+       // Build heap with greatest element at top.
+       for i := (hi - 1) / 2; i >= 0; i-- {
+               siftDown(data, i, hi, first)
+       }
+
+       // Pop elements, largest first, into end of data.
+       for i := hi - 1; i >= 0; i-- {
+               data.Swap(first, first+i)
+               siftDown(data, lo, i, first)
+       }
+}
+
 // Quicksort, following Bentley and McIlroy,
 // ``Engineering a Sort Function,'' SP&E November 1993.
 
-// Move the median of the three values data[a], data[b], data[c] into data[a].
+// medianOfThree moves the median of the three values data[a], data[b], data[c] into data[a].
 func medianOfThree(data Interface, a, b, c int) {
        m0 := b
        m1 := a
@@ -123,16 +160,21 @@ func doPivot(data Interface, lo, hi int) (midlo, midhi int) {
        return lo + b - a, hi - (d - c)
 }
 
-func quickSort(data Interface, a, b int) {
+func quickSort(data Interface, a, b, maxDepth int) {
        for b-a > 7 {
+               if maxDepth == 0 {
+                       heapSort(data, a, b)
+                       return
+               }
+               maxDepth--
                mlo, mhi := doPivot(data, a, b)
                // 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)
+                       quickSort(data, a, mlo, maxDepth)
                        a = mhi // i.e., quickSort(data, mhi, b)
                } else {
-                       quickSort(data, mhi, b)
+                       quickSort(data, mhi, b, maxDepth)
                        b = mlo // i.e., quickSort(data, a, mlo)
                }
        }
@@ -141,7 +183,16 @@ func quickSort(data Interface, a, b int) {
        }
 }
 
-func Sort(data Interface) { quickSort(data, 0, data.Len()) }
+func Sort(data Interface) {
+       // Switch to heapsort if depth of 2*ceil(lg(n)) is reached.
+       n := data.Len()
+       maxDepth := 0
+       for 1<<uint(maxDepth) < n {
+               maxDepth++
+       }
+       maxDepth *= 2
+       quickSort(data, 0, data.Len(), maxDepth)
+}
 
 func IsSorted(data Interface) bool {
        n := data.Len()