排序五：归并排序

 1 using System;
 2 using System.Collections.Generic;
 3 using System.Linq;
 4 using System.Text;
 5 using System.Threading.Tasks;
 6 
 7 namespace Sort
 8 {
 9     class Program
10     {
11         static void Main(string[] args)
12         {
13             List<int> list = new List<int>();
14             Random rd = new Random();
15             for (int i = 0; i < 10; i++)
16             {
17                 list.Add(rd.Next(100));
18             }
19             List<int> successList = Sort(list);
20             foreach (int i in successList)
21             {
22                 Console.WriteLine(i);
23             }
24         }
25 
26         /// <summary>
27         /// 进行递归二分排序
28         /// </summary>
29         static List<int> Sort(List<int> list)
30         {
31             //递归出口
32             if (list.Count <= 1)
33             {
34                 return list;
35             }
36 
37             int mid = list.Count / 2;
38             List<int> left = new List<int>();
39             List<int> right = new List<int>();
40             for (int i = 0; i < mid; i++)
41             {
42                 left.Add(list[i]);
43             }
44             for (int i = mid; i < list.Count; i++)
45             {
46                 right.Add(list[i]);
47             }
48             left = Sort(left);
49             right = Sort(right);
50             return Merge(left, right);
51         }
52 
53         /// <summary>
54         /// 合并已经排好序的List
55         /// </summary>
56         static List<int> Merge(List<int> left, List<int> right)
57         {
58             List<int> temp = new List<int>();
59             while (left.Count > 0 && right.Count > 0)
60             {
61                 if (left[0] > right[0])
62                 {
63                     temp.Add(right[0]);
64                     right.RemoveAt(0);
65                 }
66                 else
67                 {
68                     temp.Add(left[0]);
69                     left.RemoveAt(0);
70                 }
71             }
72             if (left.Count > 0)
73             {
74                 foreach (int i in left)
75                 {
76                     temp.Add(i);
77                 }
78             }
79             if (right.Count > 0)
80             {
81                 foreach (int i in right)
82                 {
83                     temp.Add(i);
84                 }
85             }
86             return temp;
87         }
88     }
89 }