Consider an array of n Lego objects. Each Lego has a method colour() that returns the value red, blue, or white.

Write in pseudo-code a linear-time algorithm that rearranges an array of Lego so that the red Lego objects come first, the blue Lego objects come next, and the white Lego objects some last.

No single step should hide something that is more than O(1) (unless it is a call to some method given or that you have written and it is stated what the runtime is).

The pseudo-code program is clearly enough described that a Java programmer could trivially rewrite it as a Java program with virtually no thinking about any of the details of the pseudo-code algorithm.

Explain briefly, but convincingly, why your algorithm is O(n).