An array A holds n integers, and all integers in A belong to the set {0,1,2}. Describe an O(n) sorting algorithm for putting A in sorted order. Your algorithm may not make use of auxiliary storage such as arrays or hash tables. More precisely, the only additional space used, beyond the given array is O(1). Give an argument to explain why your algorithm runs in O(n) time.
This is a self-answered question, but other answers are certainly desired.