From a3df3cda2499d993979b99e5cdc6b9ac695a8587 Mon Sep 17 00:00:00 2001 From: kientzle Date: Tue, 11 Nov 2003 04:59:23 +0000 Subject: Improve the performance of radixsort() when sorting strings with common prefixes by noting when all the strings land in just one bin. Testing shows significant speedups (on the order of 30%) on strings with common prefixes and no slowdowns on any of my test cases. Submitted by: Markus Bjartveit Kruger PR: 58860 Approved by: gordon (mentor) --- lib/libc/stdlib/radixsort.c | 11 +++++++++++ 1 file changed, 11 insertions(+) (limited to 'lib/libc/stdlib/radixsort.c') diff --git a/lib/libc/stdlib/radixsort.c b/lib/libc/stdlib/radixsort.c index de5cd4b..9334744 100644 --- a/lib/libc/stdlib/radixsort.c +++ b/lib/libc/stdlib/radixsort.c @@ -177,6 +177,17 @@ r_sort_a(a, n, i, tr, endch) } /* + * Special case: if all strings have the same + * character at position i, move on to the next + * character. + */ + if (nc == 1 && count[bmin] == n) { + push(a, n, i+1); + nc = count[bmin] = 0; + continue; + } + + /* * Set top[]; push incompletely sorted bins onto stack. * top[] = pointers to last out-of-place element in bins. * count[] = counts of elements in bins. -- cgit v1.1