1class MergeSortSample
 2    {
 3        public void MergeSort(int[] values, int begin, int end)
 4        {
 5            if (begin < end)
 6            {
 7                int mid = (begin + end) / 2;
 8                MergeSort(values, begin, mid);
 9                MergeSort(values, mid + 1, end);
10                Merge(values, begin, mid, end);                
11            }
12        }
13
14        public void Merge(int[] values, int begin, int mid, int end)
15        {
16            int length1 = mid - begin + 1;
17            int length2 = end - mid;
18            int[] values1 = new int[length1 + 1];
19            int[] values2 = new int[length2 + 1];
20            for (int i = 0; i < length1; i++)
21            {
22                values1[i] = values[i + begin];
23            }
24            for (int i = 0; i < length2; i++)
25            {
26                values2[i] = values[i + mid + 1];
27            }
28
29            values1[length1] = int.MaxValue;
30            values2[length2] = int.MaxValue;
31                        
32            for (int i = 0, j = 0, k = begin; k <= end; ++k)
33            {
34                if (values1[i] <= values2[j])
35                {
36                    values[k] = values1[i];
37                    ++i;
38                }
39                else
40                {
41                    values[k] = values2[j];
42                    ++j;
43                }
44            }
45        }
46
47        static void Main()
48        {
49            int[] values = { 4, 3, 7, 5, 8, 9, 0, 1, 2, 6 };
50
51            MergeSortSample mergeSort = new MergeSortSample();
52            mergeSort.MergeSort(values, 0, values.Length - 1);
53
54            foreach (int v in values)
55            {
56                Console.Write(v + " ");
57            }
58            Console.ReadKey();
59        }
60    }