I stumbled upon the Dutch National Flag problem posed by Djikstra today. It's a very interesting problem. The elegant solution in the wikipedia implements over one iteration of quicksort operating with two pivots. It's an O(n) solution.