fix heapsort

git-svn-id: http://skia.googlecode.com/svn/trunk@126 2bbb7eff-a529-9590-31e7-b0007b416f81

1 files changed, 17 insertions, 32 deletions

diff --git a/src/core/SkTSort.h b/src/core/SkTSort.h
index fba49e214f..d9544d78ad 100644
--- a/src/core/SkTSort.h
+++ b/src/core/SkTSort.h
@@ -21,44 +21,29 @@
 #include "SkTypes.h"
 
 template <typename T>
-void SkTHeapSort_SiftDown(T array[], int root, int bottom)
-{
-    int root2 = root << 1;
-
-    while (root2 <= bottom)
-    {
-        int maxChild;
-
-        if (root2 == bottom)
-            maxChild = root2;
-        else if (array[root2] > array[root2 + 1])
-            maxChild = root2;
-        else
-            maxChild = root2 + 1;
-
-        if (array[root] < array[maxChild])
-        {
-            SkTSwap<T>(array[root], array[maxChild]);
-            root = maxChild;
-            root2 = root << 1;
+void SkTHeapSort_SiftDown(T array[], int root, int bottom) {
+    while (root*2 + 1 <= bottom) {
+        int child = root * 2 + 1;
+        if (child+1 <= bottom && array[child] < array[child+1]) {
+            child += 1;
         }
-        else
+        if (array[root] < array[child]) {
+            SkTSwap<T>(array[root], array[child]);
+            root = child;
+        } else {
             break;
+        }
     }
 }
 
-template <typename T>
-void SkTHeapSort(T array[], int count)
-{
+template <typename T> void SkTHeapSort(T array[], int count) {
     int i;
-
-    for (i = count/2 - 1; i >= 0; --i)
-        SkTHeapSort_SiftDown<T>(array, i, count);
-
-    for (i = count - 2; i >= 0; --i)
-    {
-        SkTSwap<T>(array[0], array[i + 1]);
-        SkTHeapSort_SiftDown<T>(array, 0, i);
+    for (i = count/2 - 1; i >= 0; --i) {
+        SkTHeapSort_SiftDown<T>(array, i, count-1);
+    }
+    for (i = count - 1; i > 0; --i) {
+        SkTSwap<T>(array[0], array[i]);
+        SkTHeapSort_SiftDown<T>(array, 0, i-1);
     }
 }