Built in sort() method of python

Question

Possible Duplicate:
About python’s built in sort() method

Which of the sorting algorithms does the sort() method use to sort a list of numbers? How can I prove it?

seq = list_of_numbers
seq.sort()

As a side note, You probably mean, "Which algorithm does cpython's `sort` method use". A python *implementation* is free to use whatever sorting algorithm that it wants provided that the algorithm is stable. — mgilson, Jan 09 '13 at 13:33
@mgilson: Jython uses `Collections.sort()` (so presumably that's also TimSort). Looking for IronPython now.. — Martijn Pieters, Jan 09 '13 at 13:42
@MartijnPieters -- Timsort is good. I suspect that they all use it. I just wanted to point out (again) that `cpython` *is not python*. It's an implementation and OP is asking about an *implementation detail*. — mgilson, Jan 09 '13 at 13:49
@mgilson: Yup, I know; just tickled into looking for the implementations. I can honestly say that "I was there" when Tim invented TimSort (we were working at the same company at the time), so I feel a certain affinity. :-) — Martijn Pieters, Jan 09 '13 at 13:53
@mgilson: after some distractions, found the IronPython list implementation. It uses merge sort (I am all disappointed now). — Martijn Pieters, Jan 09 '13 at 14:16
@mgilson: and pypy is using TimSort again: https://bitbucket.org/pypy/pypy/src/tip/pypy/rlib/listsort.py — Martijn Pieters, Jan 09 '13 at 14:19

score 9 · Accepted Answer · answered Jan 09 '13 at 13:24

It uses TimSort, an algorithm developed for Python by Tim Peters (of Zen of Python fame).

It is a hybrid of Merge and Insertion sort, and now also in use in Java and Android. The Python source code includes a more detailed description. You'll find the implementation in the listobject.c C source.

score 1 · Answer 2 · answered Jan 09 '13 at 13:24

1

The easiest way to determine the sorting algorithm and to prove you're correct is look at the source.

answered Jan 09 '13 at 13:24

John Percival Hackworth

11,395
2
29
38

score 0 · Answer 3 · edited May 23 '17 at 12:18

0

This may enlight you. http://www.daniweb.com/software-development/python/code/216689/sorting-algorithms-in-python

You can prove it by showing the c code under the hood.

This is almost your same question. About Python's built in sort() method

edited May 23 '17 at 12:18

Community

1
1

answered Jan 09 '13 at 13:27

MGP

2,981
35
34

Built in sort() method of python

3 Answers3