Index: sys/conf/files
===================================================================
--- sys/conf/files
+++ sys/conf/files
@@ -3427,6 +3427,8 @@
 libkern/memmem.c		optional gdb
 libkern/qsort.c			standard
 libkern/qsort_r.c		standard
+libkern/mergesort.c		standard
+libkern/mergesort_r.c		standard
 libkern/random.c		standard
 libkern/scanc.c			standard
 libkern/strcasecmp.c		standard
Index: sys/libkern/mergesort.c
===================================================================
--- sys/libkern/mergesort.c
+++ sys/libkern/mergesort.c
@@ -0,0 +1,105 @@
+/*-
+ * Copyright (c) 2016 Hans Petter Selasky. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#include <sys/cdefs.h>
+__FBSDID("$FreeBSD$");
+
+#include <sys/param.h>
+#include <sys/libkern.h>
+
+/*
+ * This mergesort algorithm preserves the order of the elements it
+ * sorts. The complexity of the algorithm is O(log2(N) * N) and the
+ * stack space is predictable.
+ */
+
+#ifdef I_AM_MERGESORT_R
+void
+mergesort_by_pointer_r(void **base, void **tmp, size_t nmemb, void *thunk,
+    int (*cmp)(void *, const void *, const void *))
+#else
+void
+mergesort_by_pointer(void **base, void **tmp, size_t nmemb,
+    int (*cmp)(const void *, const void *))
+#endif
+{
+	size_t x;
+	size_t y;
+
+	/* select partition size */
+	for (x = 1; x < nmemb; x *= 2) {
+		/* iterate all the partitions */
+		for (y = 0; (y + x) < nmemb; y += 2 * x) {
+			size_t a;
+			size_t b;
+			size_t c;
+			size_t d;
+
+			a = 0;		/* lower index */
+			b = x;		/* upper index */
+			c = y;		/* partition start */
+			d = 2 * x;	/* partition length */
+
+			/* check if upper partition is too small */
+			if (d > (nmemb - y))
+				d = (nmemb - y);
+
+			/* skip if partittions are back to back */
+			if (cmp(
+#ifdef I_AM_MERGESORT_R
+			    thunk,
+#endif
+			    base + c + b - 1,
+			    base + c + b) <= 0)
+				continue;
+
+			/* copy data to temporary buffer */
+			memcpy(tmp, base + c, d * sizeof(void *));
+
+			/* merge sort - preserving the sequence of the elements */
+			while (1) {
+				if (a == x) {
+					memcpy(base + c,
+					    tmp + b, (d - b) * sizeof(void *));
+					break;
+				} else if (b == d) {
+					memcpy(base + c,
+					    tmp + a, (x - a) * sizeof(void *));
+					break;
+				}
+				if (cmp(
+#ifdef I_AM_MERGESORT_R
+					thunk,
+#endif
+					tmp + a,
+					tmp + b) <= 0) {
+					base[c++] = tmp[a++];
+				} else {
+					base[c++] = tmp[b++];
+				}
+			}
+		}
+	}
+}
Index: sys/libkern/mergesort_r.c
===================================================================
--- sys/libkern/mergesort_r.c
+++ sys/libkern/mergesort_r.c
@@ -0,0 +1,28 @@
+/*-
+ * Copyright (c) 2016 Hans Petter Selasky. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ * $FreeBSD$
+ */
+#define I_AM_MERGESORT_R
+#include "libkern/mergesort.c"
Index: sys/sys/libkern.h
===================================================================
--- sys/sys/libkern.h
+++ sys/sys/libkern.h
@@ -115,6 +115,10 @@
 void	*memcchr(const void *s, int c, size_t n);
 int	 memcmp(const void *b1, const void *b2, size_t len);
 void	*memmem(const void *l, size_t l_len, const void *s, size_t s_len);
+void	 mergesort_by_pointer(void **base, void **tmp, size_t nmemb,
+	    int (*compar)(const void *, const void *));
+void	 mergesort_by_pointer_r(void **base, void **tmp, size_t nmemb, void *thunk,
+	    int (*compar)(void *, const void *, const void *));
 void	 qsort(void *base, size_t nmemb, size_t size,
 	    int (*compar)(const void *, const void *));
 void	 qsort_r(void *base, size_t nmemb, size_t size, void *thunk,