Merge tag 'trace-v6.9-2' of git://git.kernel.org/pub/scm/linux/kernel/git/trace/linux...

[sfrench/cifs-2.6.git] / lib / sort.c

diff --git a/lib/sort.c b/lib/sort.c
index b399bf10d6759b47c5ed28a1ff0bd3cd4d26b00c..a0509088f82aa57cad934d650960a12e55144a64 100644 (file)
--- a/lib/sort.c
+++ b/lib/sort.c
@@ -215,6 +215,7 @@ void sort_r(void *base, size_t num, size_t size,
        /* pre-scale counters for performance */
        size_t n = num * size, a = (num/2) * size;
        const unsigned int lsbit = size & -size;  /* Used to find parent */
+       size_t shift = 0;
 
        if (!a)         /* num < 2 || size == 0 */
                return;
@@ -242,12 +243,21 @@ void sort_r(void *base, size_t num, size_t size,
        for (;;) {
                size_t b, c, d;
 
-               if (a)                  /* Building heap: sift down --a */
-                       a -= size;
-               else if (n -= size)     /* Sorting: Extract root to --n */
+               if (a)                  /* Building heap: sift down a */
+                       a -= size << shift;
+               else if (n > 3 * size) { /* Sorting: Extract two largest elements */
+                       n -= size;
                        do_swap(base, base + n, size, swap_func, priv);
-               else                    /* Sort complete */
+                       shift = do_cmp(base + size, base + 2 * size, cmp_func, priv) <= 0;
+                       a = size << shift;
+                       n -= size;
+                       do_swap(base + a, base + n, size, swap_func, priv);
+               } else if (n > size) {  /* Sorting: Extract root */
+                       n -= size;
+                       do_swap(base, base + n, size, swap_func, priv);
+               } else  {               /* Sort complete */
                        break;
+               }
 
                /*
                 * Sift element at "a" down into heap.  This is the
@@ -262,7 +272,7 @@ void sort_r(void *base, size_t num, size_t size,
                 * average, 3/4 worst-case.)
                 */
                for (b = a; c = 2*b + size, (d = c + size) < n;)
-                       b = do_cmp(base + c, base + d, cmp_func, priv) >= 0 ? c : d;
+                       b = do_cmp(base + c, base + d, cmp_func, priv) > 0 ? c : d;
                if (d == n)     /* Special case last leaf with no sibling */
                        b = c;