Talk:Timsort

Needs algorithms and code examples

Ideally in several programming languages so that its as accessible as possible.

This article is a stub. —Preceding unsigned comment added by Veganfanatic (talk • contribs) 20:09, 12 August 2010 (UTC)[reply]

As of algorithm it can be hard, as timsort have many additional tricks, like galloping mode when merging, two-phase marging, it also switches beetwen few modes adaptativly. I am looking at it as I like merge-sort, and was looking at timsort as practical and fast mergesort. I will keep code as small as possible.

Quality Problems

I was reading this page, and it just struck me as being very poor in an encyclopædic sense. Here's the two key things that struck me:

This page does not actually present the algorithm, nor does any of its links; all that exists is either discussion about it or a link to a patch to Java that includes an implementation of it, and that's both huge and unclear due to the large quantity of extraneous information (and the patch does a lot of other things too). You would not want to have to implement the algorithm in some other language from that starting point (which is what I'll define as the key requirement for a “practitioner-grade” algorithm description).
There wrong notation is used for describing upper-bound complexities (in both space and time); for example, upper bounds should use $\mathrm {O} (n\log n)$ rather than $\Theta (n\log n)$ (after all, it's an upper bound).

Right now, it's not useful as a source for practitioners or the general public, and nor does it indicate where appropriate material exists. –Donal Fellows (talk) 14:16, 9 August 2010 (UTC)[reply]