<p>I like to read about new and clever algorithms. And I like to think out of the box, so all kinds of algorithms from all fields of computation are welcome.</p>

<p>From time to time I read research papers to keep up with the current research and expand my horizon. I also like to learn new tricks. Unfortunately I tend to concentrate only on my field of interest, so I miss a lot of usefull stuff.</p>

<p>Let's just not post mainstream things. Instead write about something special that made you think: "Wow - now <em>that's</em> a clever solution!".</p>

I'll start with something everyone can use: introspective sort.
http://en.wikipedia.org/wiki/Introsort
A new sort algorithms that combines the best of quick, insertion and heap sort. To be exact it's not a new algorithm by itself but a
very
clever combination.
You get the speed of quick-sort up to the point where the quick-sort runs into the degenerated O(n²) case. That gets detected for almost no cost. The remaining partition get sorted using heap- or merge-sort. This not only avoids the degenerated case but creates an clear defined upper bound for stack-usage as well.
Insertion sort takes - as usual - care about all small partitions that are left over from the quick-sort pass.
For me that was a new discovery because I stopped to use quick-sort for my applications.
I do a lot of work on embedded devices and I do have to care about stack usage. Using quick-sort was always a bit risky because the faint chance that it runs amok on the stack. Even if you know that with the current data everything will be fine you never know if someone later cut'n'pastes your code into a different project and uses it for data it was never ment for.
Thanks to introspective sort I now have full control over the stack usage and get a performance boost as well.