I have recently been fascinated with the sorting. Specifically, I've been working on processing log files into nice HTML pages with graphs and the like. My first conquest in sorting was working with my Squid proxy server access logs. As I've worked through it, I've found that python has incredible resources for sorting. As I worked through the text processing, sorting through and finding the most popular sites, busiest clients, etc. I found a python module that has intrigued me called bisect

With bisect, I can create a list, sort it, and then add new elements to the sorted list in its given location. In C, this is a pretty cumbersome job, and even though it may be faster, the resulting code is much more complicated. As a matter of fact, these log files are quite large (sometimes > 1GB), and the server is only a 1GHz server, and it's still fast enough.

import bisect, random

random.seed(random.randint(1, 10))

l = []
for i in range(1, 50):
  new = random.randint(1, 200)
  bisect.insort(l, new)
  print '%d %d' % (new, l)

The above code results in a randomly generated list of numbers. However, as the numbers are inserted into the list, they are inserted at their proper index with the sort, so as not to corrupt the already sorted list. Try it out in a python shell and you'll see that the list never actually gets corrupted.

Edit: In regards to my comment about C vs. Python, there is apparently an equivalent C implementation of bisect available. If that C implementation is found, it overrides the Python module. I guess it really can be as fast as C, huh?