Implementation for http://ayende.com/blog/163394/new-interview-question, without (explicit) sorting.

faster.cs

using System;
using System.Collections.Generic;
using System.Linq;
using NUnit.Framework;

namespace CodeSamples
{
    [TestFixture]
    public class FindRunTests
    {
        [Test]
        public void TestRuns()
        {
            var test = new[] { 1, 59, 12, 43, 4, 58, 5, 13, 46, 3, 6 };
            var expected = new[] { new[] { 1 }, new[] { 3, 4, 5, 6 }, new[] { 12, 13 }, new[] { 43 }, new[] { 46 }, new[] { 58, 59 } };
            var result = FindRuns(test).ToArray();
            for (var i = 0; i < expected.Length; i++)
            {
                CollectionAssert.AreEqual(expected[i], result[i]);
            }
        }

        private IEnumerable<IEnumerable<int>> FindRuns(IEnumerable<int> pages)
        {
            var runs = new List<Run>();
            foreach (var page in pages)
            {
                var testRun = new Run { Min = page, Max = page };

                var runIndex = runs.BinarySearch(testRun);
                if (runIndex > 0) // already a run minimum, not needed if input is unique
                    continue;

                runIndex = ~runIndex;

                Run smaller = null;
                var updatedSmall = false;
                if (runIndex != 0)
                {
                    smaller = runs[runIndex - 1];
                    if (smaller.Max >= page && smaller.Min >= page)
                        continue; //already in this page, 
                    if (smaller.Max + 1 == page)
                    {
                        smaller.Max = page;
                        updatedSmall = true;
                    }
                }

                var updatedLarge = false;
                if (runIndex != runs.Count)
                {
                    var larger = runs[runIndex];
                    if (larger.Min - 1 == page)
                    {
                        if (updatedSmall)
                        {
                            //merge large and small
                            smaller.Max = larger.Max;
                            runs.RemoveAt(runIndex);
                            continue;
                        }
                        larger.Min = page;
                        updatedLarge = true;
                    }
                }

                if (!(updatedLarge || updatedSmall))
                    runs.Insert(runIndex, testRun);
            }

            foreach (var run in runs)
                yield return run.Values;
        }

        class Run : IComparable<Run>
        {
            public int Min;
            public int Max;

            public IEnumerable<int> Values => Enumerable.Range(Min, Max - Min + 1);

            public int CompareTo(Run other)
            {
                return Min.CompareTo(other.Min);
            }
        }
    }
}

gistfile1.cs

public static IEnumerable<IEnumerable<int>> GetRuns(IEnumerable<int> ints)
{
    var used = new HashSet<int>(ints);
    var min = used.Min();
    var ordered = Enumerable.Range(min, used.Max()).Where(used.Contains);

    int runStart = min;
    int runEnd = runStart;

    foreach (var num in ordered.Skip(1))
    {
        if (num != runEnd + 1)
        {
            yield return Enumerable.Range(runStart, runEnd - runStart + 1);
            runStart = num;
        }
        runEnd = num;
    }
    yield return Enumerable.Range(runStart, runEnd - runStart + 1);

}

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