A Linear Time Majority Vote Algorithm (cs.utexas.edu)

That's pretty interesting. I'm gonna write a perl script that implements it and play with it a bit.