[j-pb]

Is there a reason to use galloping over an array vs a seek in a search tree?

Better real world factors?

Galloping, Demaine set intersection, worst case optimal joins, they all seem to be different aspects of the same underlying principle.

So I'm very curious about the peculiarities in the sorting case.

[tim-peters]

See CPython's https://github.com/python/cpython/blob/main/Objects/listsort... for details about the sort. In fact, its "galloping" was inspired by a paper of which Demaine was a co-author (reference in the file already linked to).

CPython's lists are implemented as contiguous C arrays of pointers (to Python objects). Any way of grafting a tree-ish structure on top of that would be unacceptably wasteful of space and/or time. So sorting "gallops" over arrays because it's array-in, array-out.

[j-pb]

Thank you for the explanation!