[Tutor] Sorting Data

[Jeff Shannon]

Gregor Lingl wrote:

>
> Another way to accomplish this is to provide your own comparison-function
> as an argument to sort

This is another possibility, but extensive discussion on comp.lang.python some
time ago established that, in most cases, it's far more efficient to use the
decorate-sort-undecorate pattern.  Copying the list is fairly quick (you're only
copying references), and if you use the default comparison function, then all of
the comparisons are done in built-in compiled (and optimized) C code.  If you
provide your own comparison function, OTOH, then not only are the comparisons
being done in (slower) Python code, but you have an extra (slow) function call
into Python for each and every compare that you do -- and the number of compares
increases geometrically with the size of the list (I don't recall the exact order
of magnitude, but it's definately greater than linear).  So the longer the list
you're sorting, the more time it takes per item...  For particularly short lists,
a custom cmp() function may be faster, because it avoids a little bit of memory
allocation overhead, but for lists of even moderate length,
decorate-sort-undecorate takes the advantage and it only gets more significant as
the list gets longer.

Jeff Shannon
Technician/Programmer
Credit International