Is extra::sort::tim_sort stable?

[SimonSapin]

Is extra::sort::tim_sort the same algorithm as Python’s Timsort? The documentation do not say much. In particular, can I rely on this sort being stable? (servo/servo#1001 is waiting on this.)

I can provide a documentation patch this is confirmed.

[SimonSapin]

@14427, you seem to be the one who added this. Can you confirm?

[pnkfelix]

@SimonSapin according to https://en.wikipedia.org/wiki/Timsort , the method is not stable (unless elements in a run "are present in strictly descending order", which I simplify to just "it is not stable").

but then again, http://c2.com/cgi/wiki?TimSort claims that it is stable. So I guess one might have to actually read the code. :(

[SimonSapin]

I’m fairly sure that TimSort as found in Python is stable. In the Wikipedia sentence you quoted, "this method" refers not to TimSort in general but for the step of finding sub-sequence that are in reverse order. To preserve stability, this method is only used when the sub-sequence is in strictly descending order.

Although it very probably does, I just want to double-check that this code implements the same algorithm.

[thestinger]

I'm planning on writing a dead simple merge sort for libstd (dropping down to insertion sort for less than ~32 elements) and dropping the extra::sort module completely. A heap sort will be available through the priority_queue module and we just don't need all of these slow, flaky alternatives.

[SimonSapin]

@thestinger is this new sort that you’re planning stable? Also, Timsort’s property of being fast on already-sorted sub-sequences is very interesting for my use case. Is it really slow and flaky?

[thestinger]

Yes, all of the sorts in that module are slow, and none of them would need Clone if they were done well.

I think the merge sort would be stable, as a traditional merge sort and insertion sort are. It should be quite fast on already-sorted sub-sequences, likely faster than Timsort for anything without a very expensive comparison function.

[14427]

The sort is stable. I think it was faster in my benchmarks than mergesort, but they might not have been that representative of actual data.
Also, the original, unsafe implementation for timsort didn't need Clone. It got switched so that it wouldn't be doing any tricks to avoid copies.