diff options
Diffstat (limited to 'lib/sort.c')
| -rw-r--r-- | lib/sort.c | 14 |
1 files changed, 7 insertions, 7 deletions
diff --git a/lib/sort.c b/lib/sort.c index a0509088f82a..048b7a6ef967 100644 --- a/lib/sort.c +++ b/lib/sort.c @@ -5,13 +5,11 @@ * This performs n*log2(n) + 0.37*n + o(n) comparisons on average, * and 1.5*n*log2(n) + O(n) in the (very contrived) worst case. * - * Glibc qsort() manages n*log2(n) - 1.26*n for random inputs (1.63*n + * Quicksort manages n*log2(n) - 1.26*n for random inputs (1.63*n * better) at the expense of stack usage and much larger code to avoid * quicksort's O(n^2) worst case. */ -#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt - #include <linux/types.h> #include <linux/export.h> #include <linux/sort.h> @@ -252,10 +250,7 @@ void sort_r(void *base, size_t num, size_t size, 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 */ + } else { /* Sort complete */ break; } @@ -285,6 +280,11 @@ void sort_r(void *base, size_t num, size_t size, do_swap(base + b, base + c, size, swap_func, priv); } } + + n -= size; + do_swap(base, base + n, size, swap_func, priv); + if (n == size * 2 && do_cmp(base, base + size, cmp_func, priv) > 0) + do_swap(base, base + size, size, swap_func, priv); } EXPORT_SYMBOL(sort_r); |