title: Algorithm to sort three kinds of balls
body: <p>We have N balls of three different types: red(r), blue(b), and white(w).</p>
  
  <p>I need to sort them so that red balls appear firsts, then all white balls and finally all blue balls.</p>
  
  <p>Example:</p>
  
  <p>In: bwrwrbbrwwrb</p>
  
  <pre><code>string[] arrBalls = { "b", "w", "r", "w", "r", "b", "b", "r", "w", "w", "r", "b" };
  </code></pre>
  
  <p>Out:rrrrwwwwbbbb</p>
  
  <p>I need to found a linear O(n) algorithm.</p>
  
  <p><strong>Update:</strong> C# code</p>
  
  <pre><code> string[] arrBalls = { "b", "w", "r", "w", "r", "b", "b", "r", "w", "w", "r", "b" };
   int index_red = 0;
   int index_blue = arrBalls.Length - 1;
  
   for (int i = 0; i &lt; arrBalls.Length; i++)
              {
                  if (arrBalls[i] == "r" &amp;&amp; index_red != i)
                  {
                      string TempRed = arrBalls[index_red];
                      arrBalls[index_red] = arrBalls[i];
                      arrBalls[i] = TempRed;
                      if (arrBalls[index_red] == "r")
                      {
                          while(arrBalls[index_red] == "r")index_red++;
                      }
                      else
                      {
                          index_red++;
                      }
  
  
                  }
  
  
                  if (arrBalls[i] == "b" &amp;&amp; index_blue != i)
                  {
                      string TempRed = arrBalls[index_blue];
                      arrBalls[index_blue] = arrBalls[i];
                      arrBalls[i] = TempRed;
  
                      if (arrBalls[index_blue] == "b")
                      {
                          while (arrBalls[index_blue] == "b") index_blue--;
                      }
                      else
                      {
                          index_blue--;
                      }
                  }
  
  
              }
  </code></pre>