test-mergesort: add test subcommand

Adapt the qsort certification program from "Engineering a Sort Function"
by Bentley and McIlroy for testing our linked list sort function.  It
generates several lists with various distribution patterns and counts
the number of operations llist_mergesort() needs to order them.  It
compares the result to the output of a trusted sort function (qsort(1))
and also checks if the sort is stable.

Also add a test script that makes use of the new subcommand.

Signed-off-by: René Scharfe <l.s.r@web.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

1 files changed, 11 insertions, 0 deletions

diff --git a/t/t0071-sort.sh b/t/t0071-sort.sh
new file mode 100755
index 0000000000..a8ab174879
--- /dev/null
+++ b/t/t0071-sort.sh
@@ -0,0 +1,11 @@
+#!/bin/sh
+
+test_description='verify sort functions'
+
+. ./test-lib.sh
+
+test_expect_success 'llist_mergesort()' '
+	test-tool mergesort test
+'
+
+test_done