Bug in timsort!?

[Robert Kern]

On 2015-02-24 22:45, Grant Edwards wrote:
> On 2015-02-24, Roy Smith <roy at panix.com> wrote:
>
>> http://envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/
>
> I don't get it.
>
>      3.2 Corrected Python merge_collapse function
>
>      merge_collapse(MergeState *ms)
>      {
>          struct s_slice *p = ms->pending;
>
>          assert(ms);
>          while (ms->n > 1) {
>              Py_ssize_t n = ms->n - 2;
>              if (     n > 0   && p[n-1].len <= p[n].len + p[n+1].len
>                  || (n-1 > 0 &&  p[n-2].len <= p[n].len + p[n-1].len)) {
>                  if (p[n-1].len < p[n+1].len)
>                      --n;
>                  if (merge_at(ms, n) < 0)
>                      return -1;
>              }
>              else if (p[n].len <= p[n+1].len) {
>                       if (merge_at(ms, n) < 0)
>                              return -1;
>              }
>              else
>                  break;
>          }
>          return 0;
>      }
>
> Or does "Python function" mean something else in this context?

"Corrected merge_collapse function [from the Python implementation of TimSort]" 
as opposed to the Java implementation which was also discussed.

-- 
Robert Kern

"I have come to believe that the whole world is an enigma, a harmless enigma
  that is made terrible by our own mad attempt to interpret it as though it had
  an underlying truth."
   -- Umberto Eco