timsort

[xu561865]

When I used [2, 4, 5, 3, 1] to test, it just returned [1, 2, 4, 5]

[FrogBattle]

Hello,

After some play with the code I reached the following conclusion:
The 3 is left out in the following if clause :

        if lst[i] < lst[i - 1]: 
            if not new_run:
                runs.append([lst[i - 1]])
                new_run.append(lst[i])
            else:`
                runs.append(new_run)
                new_run = []

Lines 56-62.
The current index i is not assigned to "new_run" before the same variable is set to empty list, thus the 3 is lost. It is supposed to be added to the list on the next loop iteration, although this is stopped by the first check done here :

        if i == length - 1:
            new_run.append(lst[i])
            runs.append(new_run)
                break

Lines 51-54.

If you put the if clause with the break statement last, the program may add some elements to the new_run list twice. This happens as new_run initializes to [lst[0]] and it may happen that it adds some elements twice to different runs.

In general, if you rely on the next loop iteration to add the previous element into a new_run list, it must do it explicitly ( if new_run==[]), which would mean another conditional. Right now, you will not lose an element if and only if the next iterated element is also smaller than the one before him :

        if lst[i] < lst[i - 1]:
            if not new_run:
                runs.append([lst[i - 1]])
                new_run.append(lst[i])
            else:
                runs.append(new_run)
                new_run = []
        else:
            new_run.append(lst[i])

Lines 56-64.

Hope this helps.
Alex

[cclauss]

Can this issue be closed?