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
