You already got a win - quit while you're ahead ;-) Note that plain binary search here is probably not a good idea. See "listsort.txt", in the same directory as "listobject.c", for excruciating details.
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()`.
adamgordonbell|4 years ago
tim-peters|4 years ago
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()`.