合并排序是对分治法的一个完美展现,若对一个数组进行合并排序,其思路是将该数组一分为二,然后递归排序,再把两个排好序的数组合二为一,达到排序的目的;
例如对一个数组{8,3,4,6}进行排序,其过程如下:

1. {    5    3    4    6    }            //将数组一拆为二
   
2. {    5    3    }    {    4    6    }            //再次拆
   
3. {    5    }    {    3    }    {    4    }    {    6    }            //数组1和2比较,8 > 3 所以3先落位,然后是8,合并数组1和2为一个数组,数组3、4做同样的操作
   
4. {    3    5    }    {    4    6    }            //数组1和2比较，1中的第一个元素小于2中的第一，第二，所以3先落位，5大于数组2中第一个，所以接下来是数组2中的4落位，然后比较
   
5.                                                      //数组1中的5和数组2中的6，5 < 6 所以5先落位，然后剩下的6落位，得到排序好的数组
   
6. {3    4    6    8    }

复制代码

以下是实现代码，欢迎指正：

1. 
   
2.         static void MergeSort(ref int[] A)
   
3.         {
   
4.             if (A.Length > 1)
   
5.             {
   
6.                 //分
   
7.                 int[] left = new int[A.Length / 2 + A.Length % 2];
   
8.                 int[] right = new int[A.Length / 2];
   
9.                 for (int n = 0; n < (A.Length / 2 + A.Length % 2); n++)
   
10.                 {
    
11.                     left[n] = A[n];
    
12.                 }
    
13.                 for (int n = 0; n < (A.Length / 2); n++)
    
14.                 {
    
15.                     right[n] = A[(A.Length / 2) + (A.Length % 2) + n];
    
16.                 }
    
17.                 //递归
    
18.                 MergeSort(ref left);
    
19.                 MergeSort(ref right);
    
20.                 //合并,排序
    
21.                 Merge(left, right, ref A);
    
22.             }
    
23.         }
    
24. 
    
25.         static void Merge(int[] left, int[] right, ref int[] A)
    
26.         {
    
27.            
    
28.             int i = 0, j = 0, k = 0;
    
29.             while (i < left.Length && j < right.Length)
    
30.             {
    
31. 
    
32.                 if (left[i] <= right[j])
    
33.                 {
    
34.                     A[k] = left[i];
    
35.                     i++;
    
36.                 }
    
37.                 else
    
38.                 {
    
39.                     A[k] = right[j];
    
40.                     j++;
    
41.                 }
    
42.                 k++;
    
43.                 if (i == left.Length)
    
44.                 {
    
45.                     for (; j < right.Length; j++)
    
46.                     {
    
47.                         A[k] = right[j];
    
48.                         k++;
    
49.                     }
    
50.                 }
    
51.                 if(j == right.Length)
    
52.                 {
    
53.                     for (; i < left.Length; i++)
    
54.                     {
    
55.                         A[k] = left[i];
    
56.                         k++;
    
57.                     }
    
58.                 }
    
59. 
    
60.             }
    
61. 
    
62. 
    
63.         }

复制代码

多的不说了,有不对之处还请指出,
PS:觉得有些冗余,找机会在优化一下,如果有不同的看法希望不吝赐教,其他算法请看这里

合并排序是对分治法的一个完美展现,若对一个数组进行合并排序,其思路是将该数组一分为二,然后递归排序,再把两个排好序的数组合二为一,达到排序的目的;
例如对一个数组{8,3,4,6}进行排序,其过程如下:

1. {    5    3    4    6    }            //将数组一拆为二
   
2. {    5    3    }    {    4    6    }            //再次拆
   
3. {    5    }    {    3    }    {    4    }    {    6    }            //数组1和2比较,8 > 3 所以3先落位,然后是8,合并数组1和2为一个数组,数组3、4做同样的操作
   
4. {    3    5    }    {    4    6    }            //数组1和2比较，1中的第一个元素小于2中的第一，第二，所以3先落位，5大于数组2中第一个，所以接下来是数组2中的4落位，然后比较
   
5.                                                      //数组1中的5和数组2中的6，5 < 6 所以5先落位，然后剩下的6落位，得到排序好的数组
   
6. {3    4    6    8    }

复制代码

以下是实现代码，欢迎指正：

1. 
   
2.         static void MergeSort(ref int[] A)
   
3.         {
   
4.             if (A.Length > 1)
   
5.             {
   
6.                 //分
   
7.                 int[] left = new int[A.Length / 2 + A.Length % 2];
   
8.                 int[] right = new int[A.Length / 2];
   
9.                 for (int n = 0; n < (A.Length / 2 + A.Length % 2); n++)
   
10.                 {
    
11.                     left[n] = A[n];
    
12.                 }
    
13.                 for (int n = 0; n < (A.Length / 2); n++)
    
14.                 {
    
15.                     right[n] = A[(A.Length / 2) + (A.Length % 2) + n];
    
16.                 }
    
17.                 //递归
    
18.                 MergeSort(ref left);
    
19.                 MergeSort(ref right);
    
20.                 //合并,排序
    
21.                 Merge(left, right, ref A);
    
22.             }
    
23.         }
    
24. 
    
25.         static void Merge(int[] left, int[] right, ref int[] A)
    
26.         {
    
27.            
    
28.             int i = 0, j = 0, k = 0;
    
29.             while (i < left.Length && j < right.Length)
    
30.             {
    
31. 
    
32.                 if (left[i] <= right[j])
    
33.                 {
    
34.                     A[k] = left[i];
    
35.                     i++;
    
36.                 }
    
37.                 else
    
38.                 {
    
39.                     A[k] = right[j];
    
40.                     j++;
    
41.                 }
    
42.                 k++;
    
43.                 if (i == left.Length)
    
44.                 {
    
45.                     for (; j < right.Length; j++)
    
46.                     {
    
47.                         A[k] = right[j];
    
48.                         k++;
    
49.                     }
    
50.                 }
    
51.                 if(j == right.Length)
    
52.                 {
    
53.                     for (; i < left.Length; i++)
    
54.                     {
    
55.                         A[k] = left[i];
    
56.                         k++;
    
57.                     }
    
58.                 }
    
59. 
    
60.             }
    
61. 
    
62. 
    
63.         }

复制代码

多的不说了,有不对之处还请指出,
PS:觉得有些冗余,找机会在优化一下,如果有不同的看法希望不吝赐教,其他算法请看这里