computer science, math, programming and other stuff
a blog by Christopher Swenson

Brilliant programming

Often, I like to read articles on particularly insightful programming techniques or algorithms. Sometimes these algorithms are for some fairly mundane things, like searching and sorting. (So mundane, of course, that Knuth wrote a whole book about it.)

Two pieces I have enjoyed recently.

First, timsort – the sorting algorithm used by Python. It describes an interesting approach to mergesort that is stable and incredibly fast, especially for "almost" sorted arrays.

Second is a class: strlen(), from glibc. strlen(), for you non-C programmers, finds the length of a null-terminated string. So, simply, given a location in memory, it finds the next zero byte. Sounds easy? Well, it is, but there are several tricks you can to do speed up the search by quite a bit.

Any other favorite snippets of code out there?