Re:Timsort is a sorting algorithm that is efficient for real...
by aidenn0 on Sunday July 01, 2018 @05:39PM
(#17437770)
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.
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.