libc: Implement bsort(3) a bitonic type of sorting algorithm.

The bsort(3) algorithm works by swapping objects, similarly to qsort(3),
and does not require any significant amount of additional memory.

The bsort(3) algorithm doesn't suffer from the processing time issues
known the plague the qsort(3) family of algorithms, and is bounded by
a complexity of O(log2(N) * log2(N) * N), where N is the number of
elements in the sorting array. The additional complexity compared to
mergesort(3) is a fair tradeoff in situations where no memory may
be allocated.

The bsort(3) APIs are identical to those of qsort(3), allowing for
easy drop-in and testing.

The design of the bsort(3) algorithm allows for future parallell CPU
execution when sorting arrays. The current version of the bsort(3)
algorithm is single threaded. This is possible because fixed areas
of the sorting data is compared at a time, and can easily be divided
among different CPU's to sort large arrays faster.

Reviewed by:	gbe@, delphij@, pauamma_gundo.com (manpages)
Sponsored by:	NVIDIA Networking
Differential Revision:	https://reviews.freebsd.org/D36493

1 files changed, 4 insertions, 0 deletions

diff --git a/lib/libc/stdlib/Symbol.map b/lib/libc/stdlib/Symbol.map
index a105f781734d..50583a30ad3d 100644
--- a/lib/libc/stdlib/Symbol.map
+++ b/lib/libc/stdlib/Symbol.map
@@ -126,6 +126,10 @@ FBSD_1.6 {
 };
 
 FBSD_1.7 {
+	bsort;
+	bsort_b;
+	bsort_r;
+	bsort_s;
 	clearenv;
 	qsort_r;
 	secure_getenv;