Solution for http://ayende.com/blog/163394/new-interview-question

Demo.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;

namespace Demo
{
    static class Program
    {
        public struct Run
        {
            public int Start;
            public int End;
            public Run(int start, int end)
            {
                Start = start;
                End = end;
            }
        }

        public static IEnumerable<Run> GetRuns(this int[] n)
        {
            Array.Sort(n);
            int pos = 0;
            Action<int> update = (j) => pos = j;
            while (pos < n.Length - 1)
                yield return GetNextRun(n, pos, update);
        }

        private static Run GetNextRun(int[] n, int pos, Action<int> update)
        {
            int i, j, first = n[pos];
            for(j = pos + 1; j < n.Length; j++)
            {
                i = n[j];
                if (i == first + 1)
                    first = i;
                else
                    break;
            }
            update(j);
            return new Run(pos, j);
        }

        static void Main(string[] args)
        {
            Test1();
            //Test2();

            Console.ReadLine();
        }

        private static void Print(int[] n, Run run)
        {
            bool first = true;
            Console.Write('{');
            for (int i = run.Start; i < run.End; i++)
            {
                if (!first)
                    Console.Write(',');
                else
                    first = false;
                Console.Write(n[i]);
            }
            Console.WriteLine('}');
        }

        private static void Test1()
        {
            int[] n = { 1, 59, 12, 43, 4, 58, 5, 13, 46, 3, 6 };
            var runs = n.GetRuns();
            foreach (var run in runs)
                Print(n, run);
        }

        private static void DummyPrint(int[] n, Run run) { }

        private static void Test2()
        {
            const int size = 10 * 1024 * 1024;
            int[] n = new int[size];
            var rand = new Random();
            for (int i = 0; i < size; i++)
                n[i] = rand.Next();
            
            var sw = System.Diagnostics.Stopwatch.StartNew();

            var runs = n.GetRuns();
            foreach (var run in runs)
                DummyPrint(n, run);

            sw.Stop();
            Console.WriteLine(sw.Elapsed.TotalMilliseconds + "ms");
        }
    }
}