Dutch National Flag

namespace DutchFlagAlgorithm {
    using System;
    using System.Linq;

    public class Pebble{
        public enum Colors {Red = 0, White = 1, Blue = 2 };

        public Colors Color { get; }

        public Pebble(Colors c){
            Color = c;
        }

        public static implicit operator string(Pebble a) {
            switch (a.Color) {
                case Colors.Red:
                    return "R";
                case Colors.Blue:
                    return "B";
                case Colors.White:
                    return "W";
                default:
                    throw new ArgumentOutOfRangeException();
            }
        }
    }

    public class DutchFlag{
        // Swap the pebbles at i and j
        private static Pebble[] Swap(Pebble[] a, int i, int j){
            var t = a[i];
            a[i] = a[j];
            a[j] = t;
            return a;
        }

        // We want to sort a such that all the pebbles are arranged to be in the following order:
        //    red, white, Blue
        // all while remaining in O(n) time.
        public static Pebble[] Sort(Pebble[] a){
            var n = a.Length;
            var r = -1; // last index of reds
            var b = n; // first index of blues

            if(n < 2) return a;

            // Scan until we reach a non-red, and mark the index
            for(var i = 0; i < n; i++)
                if(a[i].Color != Pebble.Colors.Red) {
                    // handle the specific case where there isn't a red in front
                    if (i == 0) r = -1;
                    else r = Math.Max(r - 1, 0);
                    break;
                }
            if(r == n) return a; // return if all reds

            // Scan from the other side until we reach a non-blue and mark the index.
            for(var i = n - 1; i > r; i--)
                if(a[i].Color != Pebble.Colors.Blue){
                    b = i + 1;
                    break;
                }
            if(b == r + 1) return a; // return if all reds and blues

            // sort the remaining out of place pebbles in the middle.
            for(var i = r + 1; i < b; i++){
                while (a[i].Color != Pebble.Colors.White) {
                    if (a[i].Color == Pebble.Colors.Red) {
                        a = Swap(a, i, r + 1);
                        r++;
                        if (i == r) break;
                    }
                    else if(a[i].Color == Pebble.Colors.Blue){
                        a = Swap(a, i, b - 1);
                        b--;
                        if (i == b) break;
                    }
                }
            }
            return a;
        }

        public static void Main() {
            var r = new Random();
            for (var i = 0; i < 5; i++) {
                var a = Enumerable.Range(0, 10).Select(_ => new Pebble((Pebble.Colors) r.Next(0, 3))).ToArray();
                foreach(var p in a) Console.Write(p);
                Console.WriteLine();
                a = Sort(a);
                foreach(var p in a) Console.Write(p);
                Console.Write("\n\n");
            }
        }
    }
}