Question

What is wrong with my merge_sort in python? I've been trying for a day to get mergesort right :(

http://ideone.com/T8A5K

Answer 1

I've been using pdb for hours in vain :(

Answer 2

http://ideone.com/W3omo

fixed it!

Answer 3

how do I make it faster? the native Python timsort is really really fast on lists, while my code takes 2 seconds to sort that reversed list of 100000 integers, list.sort() takes about 0.02 seconds

Answer 4

is it because the native sorting algorithm is in C?

Answer 5

and written by better programmers than me :-D

Answer 6

numpy (a python module that's a MATLAB clone for python) array's sort is also fast.

Answer 7

Well, a couple of things. numpy presumably has an array sort optimized for numbers. If you know you have integers, you can code a faster sort (see Radix sort) that isn't limited to O(n log n) performance. Python's built-in sort is certainly written in C, yes, so that will help.

It does sound like yours is two orders of magnitude slower, but that's within the realm of possibility for C vs Python.

Answer 8

One of the things in life that isn't fair is that most, if not all, interpreted languages are implemented in C. Basically, this translates into you don't want to do interesting implementations if you can shoehorn the problem into native data structures and functions, because yours will be a dog by comparison.

Answer 9

Aren't there any other languages other than C (besides C++ and perhaps FORTRAN) with compilers that can spit out really speedy native code (comparable to C)

Answer 10

The JVM is extremely good, but it doesn't usually spit out native code (gcj is one compiler that is capable of doing so). The JVM does optimizations at runtime that make code eventually run at or faster than C speed (because it can do runtime analysis of code use to optimize).

That said, you rarely care about performance at the level where you'll need to switch to C, unless you're working embedded systems or computer games (and even games sometimes can afford to use non-C). The gain from using a dynamic language is typically valuable enough in development time that you can afford to throw more hardware at the smaller scaling problem to deal with speed issues. Additionally, you can always optimize hotspots in C in an interpreted language while sticking to the dynamic language everywhere else.

Also, note that there are ports of certain languages that run faster on the JVM—JRuby, for example.

Answer 11

There are a few other frontends to gcc. http://www.gnu.org

Answer 12

It took a while to find the frontends for GCC: http://directory.fsf.org/wiki?title=Special:Ask&offset=0&limit=100&q= [[Software-development%3A%3Acompiler%0A]]&p=mainlabel%3D%2Fformat%3Dtemplate%2Ftemplate%3DGetlist-2Drow%2Flink%3Dnone%2Fcolumns%3D1%2Fintrotemplate%3DGetlist-2Dintro%2Foutrotemplate%3DGetlist-2Doutro&po=%3FFull+description%3DDescription%0A%3FHomepage+URL%3DHomepage%0A%3FLicense%0A%3FIs+GNU%23[[File%3AHeckert_gnu.small.png|20px]]%2C%3DGNU%3F%0A

I have got to try GCJ.