2 ms·
It was not apparent from your article how Timsort ensures stability. After doing some reading on my own I was able to discover that it is done so by only rever
by aidenn0 8y ago
It was not apparent from your article how Timsort ensures stability. After doing some reading on my own I was able to discover that it is done so by only reversing strictly decreasing runs, and by never reordering runs.
While your description covers both of those points[1], it didn't mention them together as contributing to stability.
1: Actually rereading to make sure I didn't miss anything, you have a mistake, as you say: "Runs have to be strictly increasing or decreasing" while they have to be either monotonically increasing (i.e. non-decreasing) or strictly decreasing.
so: 1,2,2,3 is a run, but 3,2,2,1 is not.