[PATCH 6/9] test-mergesort: add unriffle_skewed mode

Add a mode that turns a sorted list into adversarial input for a bottom-up mergesort implementation that doubles the length of sorted sublists at each level -- like our llist_mergesort().

While unriffle mode splits the list in half at each recursion step, unriffle_skewed splits it into 2^l items and the rest, with 2^l being the highest power of two smaller than the number of items and thus 2^l >= rest. The rest is unriffled with the tail of the first half to require a merge to compare the maximum number of elements.

It complements the unriffle mode, which targets balanced merges. If the number of elements is a power of two then both actually produce the same result, as 2^l == rest == n/2 at each recursion step in that case.

Here are the results:

   $ t/helper/test-tool mergesort test | awk '
      $7 > max[$3] {max[$3] = $7; line[$3] = $0}
      END {for (n in line) print line[n]}
   '

distribut mode n m get_next set_next compare verdict sawtooth unriffle_skewed 100 128 1184 700 589 OK sawtooth unriffle_skewed 1023 1024 16373 10230 9207 OK sawtooth unriffle 1024 1024 16384 10240 9217 OK sawtooth unriffle_skewed 1025 2048 18454 11275 10241 OK

The sawtooth distribution with m>=n produces a sorted list and unriffle_skewed mode turns it into adversarial input for unbalanced merges, which it wins in all cases except for n=1024 -- the resulting list is the same, but unriffle is tested before unriffle_skewed, so its result is selected by the AWK script.

Signed-off-by: René Scharfe <l.s.r@web.de>
---
 t/helper/test-mergesort.c | 28 ++++++++++++++++++++++++++++
 1 file changed, 28 insertions(+)