Linearization post-processing (O(n^2) fancy chunking)

Implementation
7

FWIW, experimentally it seems that ancestor sort will optimally sort every cluster up to 4 transactions, and post-processing according to the algorithm above does not change that.

The simplest cluster that I’ve been able to find which does not sort optimally under ancestor sort (with or without post-processing) is this:

graph BT
   T0["B: 5"] --> T1;
   T1["A: 1"];
   T2["C: 5"] --> T1;
   T3["D: 3"];
   T4["E: 4"] --> T2;
   T4 --> T3;
  • Ancestor sort yields [A,C,D,E,B], chunked as [ACDEB] (ACDE is picked first, but then B is chunked together with it).
  • Optimal sort is [A,B,C,D,E], chunked as [ABC,DE].