// http://upload.wikimedia.org/wikipedia/commons/c/cc/Merge-sort-example-300px.gif

using System;

​

public class SortProblem

{

    public static void Main()

    {

        var a = new[] { 11, 86, 232, 28, 8, 145, 588, 1, 307, 179, 77, 792, 693, 678, 481, 888, 574, 695, 624, 866, 467, 434, 907, 259, 130, 37, 25, 373, 214, 268, 108, 672, 371, 866, 863, 279, 22, 233, 336, 830, 374, 439, 144, 234, 360, 617, 244, 5, 566, 847, 476, 493, 56, 618, 202, 576, 179, 972, 898, 970, 119, 214, 786, 38, 71, 404, 420, 827, 814, 201, 865, 341, 358, 794, 492, 27, 290, 672, 899, 512, 792, 20, 807, 367, 792, 615, 616, 753, 663, 287, 99, 49, 334, 366, 711, 160, 652, 105, 162, 955};

        var b = Sort(a);

        PrintArray(b);

    }

​

    public static int[] Sort(int[] a)

    {

        return Sort(a, 0, a.Length - 1);

    }

    public static int[] Sort(int[] a, int l, int r)

    {

        if (l == r)

        {

            return new int[]{a[l]};

        }

        int[] sortedA = Sort(a, l, (l + r) / 2);

        int[] sortedB = Sort(a, (l + r) / 2 + 1, r);

​

        int[] sorted = new int[r - l + 1];

        int iA = 0;

        int iB = 0;

        for(int i = 0; i < sorted.Length; i++)

        {

            if (iA == sortedA.Length) sorted[i] = sortedB[iB++];

            else if (iB == sortedB.Length) sorted[i] = sortedA[iA++];

            else

                sorted[i] = (sortedA[iA] < sortedB[iB]) ? sortedA[iA++] : sortedB[iB++];

        }

        return sorted;

    }

​

    public static void PrintArray(int[] a)

    {

        foreach (var item in a)

            Console.Write("{0} ", item);

        Console.WriteLine();

    }

}