Haha. AdamMerge works for me - I get enough abuse for naming a sort after myself ;-)
If you pursue this, you can probably throw out piles of the CPython code. That's
trying to keep the result "in place", so has major code near-duplication to merge "into the left side" or "into the right side", to minimize the amount of
temp memory needed (this depends on which input list is shorter).
But you're writing your output to a new list, so those cases are the same to you.
To keep the sort stable in all cases, though, you still need to distinguish between `gallop_left()` and `gallop_right()`.
If you pursue this, you can probably throw out piles of the CPython code. That's trying to keep the result "in place", so has major code near-duplication to merge "into the left side" or "into the right side", to minimize the amount of temp memory needed (this depends on which input list is shorter).
But you're writing your output to a new list, so those cases are the same to you.
To keep the sort stable in all cases, though, you still need to distinguish between `gallop_left()` and `gallop_right()`.