Timsort in Cpython

[Ian Kelly]

On Wed, Jun 19, 2013 at 11:18 AM,  <sean.westfall at gmail.com> wrote:
> The second argument takes the tuple which determines which varialble(key) to use the comparator on. And the third determines whether to return the list in ascending or descending order.

That's not exactly correct.  The arguments are listed in that order,
but in fact the arguments to list.sort are keyword-only and cannot be
supplied positionally.  So the "args" argument is expected to be an
empty tuple, and the "kwds" argument is a dict that contains both the
"key" and "reverse" arguments, if they were supplied.

> But how do these PyObject* look in C?

It's a pointer to a struct that contains information like the class
and reference count of the object.

> How does a PyListObject* look declared in CPython.

That's a pointer to a larger struct that shares the same header as the
PyObject* struct (which is basically how you do inheritance in C).  It
adds information like the length and capacity of the list, plus a
pointer to an array of PyObject* that stores the contents of the list.

> How would something like this list = [2, 1, 5, 6, 10] look in CPython. Or what about something more complicated -- mlist = [('A',1),('B',2),('C',3)].

To answer that question, you should really delve into the source and
see what these structs actually look like.  But the first is going to
contain an array of five PyObject* values, each of which references an
int, while the second is going to contain an array of three PyObject*
values, each of which references a tuple.

I also recommend that you read the sections of the Python docs that
cover the C API, as those should help you understand how these structs
are normally handled.