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 <markusk@pvv.ntnu.no>
PR: 58860
Approved by: gordon (mentor)

1 files changed, 11 insertions, 0 deletions

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.