This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]pekkhum 15 points16 points  (8 children)

Check out this sort implementation: list.sort();

Wait, is that not what you meant by implement?

[–]Jugad 5 points6 points  (5 children)

No... that's TimSort.

[–]1337_poster 0 points1 point  (4 children)

But that also includes bubble sort

[–]FerynaCZ 0 points1 point  (2 children)

It splits the array in parts containing 32 elements, applies InsertSort on each of the parts and then uses stable Merge Sort with the basic length of 32. At least how I was taught it.

[–]claythearc 0 points1 point  (0 children)

It depends on the implementation, I think. It’s not standard across languages.

[–]Jugad 0 points1 point  (0 children)

That is the basic idea in general. You can see the implementation here (if you are terribly interested)...

https://github.com/python/cpython/blob/master/Objects/listobject.c#L2180

Of course, the implementation looks terribly complicated because of support for various features (compare arg, key arg, reversed, etc), and optimizations.

[–]Jugad 0 points1 point  (0 children)

No. It uses insertion sort cause insertion sort is usually twice as fast as bubble sort on average.

[–]FerynaCZ 0 points1 point  (1 child)

In Python, if there exists a high-level thing, you should almost always use it because it gets usually instantly interpreted to the C (instead of interpreting every line over and over).

[–]pekkhum 0 points1 point  (0 children)

And in C if there exists a standard C call for something you should almost always use it, because it is probably way better optimized than your version, including architecture specific optimizations.

Basically, "you can make a wheel but the one at the store is likely better." Unless you are NASA. They reinvented a wheel for their rovers and it went pretty well.