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 static IEnumerable<long> GetRuns(this int[] n)
        {
            Array.Sort(n);
            int pos = 0;
            while (pos < n.Length - 1)
            {
                int i, j, first = n[pos];
                for(j = pos + 1; j < n.Length; j++)
                {
                    if ((i = n[j]) == first + 1)
                        first = i;
                    else
                        break;
                }
                yield return Pack(pos, j);
                pos = j;
            }
        }

        private static long Pack(int start, int end)
        {
            long run = end;
            run = run << 32;
            run = run | (uint) start;
            return run;
        }

        private static void Unpack(long run, out int start, out int end) 
        {
            start = (int) (run & uint.MaxValue);
            end = (int) (run >> 32);
        }

        static void Main(string[] args)
        {
            Test1();
            //Test2();
            Console.ReadLine();
        }

        private static void Print(int[] n, long run)
        {
            bool first = true;
            Console.Write('{');
            int start;
            int end;
            Unpack(run, out start, out end);
            for (int i = start; i < 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, long run) 
        { 
            //int start;
            //int end;
            //Unpack(run, out start, out end);
        }

        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");
        }
    }
}