[PATCH 0/9] mergesort: improve tests and performance

Our mergesort for linked lists doesn't allocate temporary memory, which is nice. It is traversing the list multiple times from start to finish, though. This series teaches it to avoid that, which speeds it up considerably. But first it improves the associated test helper to exercise the code harder and to make the effect of the changes visible in terms of saved operations.

  test-mergesort: use strbuf_getline()
  test-mergesort: add sort subcommand
  test-mergesort: add test subcommand
  test-mergesort: add generate subcommand
  test-mergesort: add unriffle mode
  test-mergesort: add unriffle_skewed mode
  p0071: measure sorting of already sorted and reversed files
  p0071: test performance of llist_mergesort()
  mergesort: use ranks stack

 mergesort.c               | 121 +++++++------
 t/helper/test-mergesort.c | 360 +++++++++++++++++++++++++++++++++++++-
 t/perf/p0071-sort.sh      |  40 ++++-
 t/t0071-sort.sh           |  11 ++
 4 files changed, 465 insertions(+), 67 deletions(-)
 create mode 100755 t/t0071-sort.sh

-- 2.33.0