# C＃，单向链表（Simply Linked List）的归并排序（Merge Sort）算法与源代码

（1）单个结点创建非常方便，普通的线性内存通常在创建的时候就需要设定数据的大小；
（2）结点的删除非常方便，不需要像线性结构那样移动剩下的数据；
（3）结点的访问方便，可以通过循环或者递归的方法访问到任意数据，但是平均的访问效率低于线性表；

Step 1：将n个元素分成两个含n/2元素的子序列
Step 2：用MS将两个子序列递归排序（最后可以将整个原序列分解成n个子序列）
Step 3：合并两个已排序好的序列

源程序：

``````using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;

namespace Legalsoft.Truffer.Algorithm
{
/// <summary>
/// 适用于单向列表的归并排序算法
/// </summary>
public partial class LinkedList
{
#region 算法1
{
if (a == null)
{
return b;
}
if (b == null)
{
return a;
}
if (a.Data <= b.Data)
{
result = a;
result.Next = Merge_Utlility(a.Next, b);
}
else
{
result = b;
result.Next = Merge_Utlility(a, b.Next);
}
return result;
}

{
if (h == null || h.Next == null)
{
return h;
}

LinkNode middle = Tortoise_And_Hare(h);
LinkNode nextofmiddle = middle.Next;

middle.Next = null;

LinkNode left = Merge_Sort(h);

LinkNode right = Merge_Sort(nextofmiddle);

LinkNode sortedlist = Merge_Utlility(left, right);
return sortedlist;
}

{
if (h == null)
{
return h;
}
LinkNode fastptr = h.Next;
LinkNode slowptr = h;

while (fastptr != null)
{
fastptr = fastptr.Next;
if (fastptr != null)
{
slowptr = slowptr.Next;
fastptr = fastptr.Next;
}
}
return slowptr;
}

{
}
#endregion

#region 算法2
{
if (head.Next == null)
{
}
mid.Next = null;

}

{
LinkNode temp = merged;

while (a != null && b != null)
{
if (a.Data < b.Data)
{
temp.Next = a;
a = a.Next;
}
else
{
temp.Next = b;
b = b.Next;
}
temp = temp.Next;
}

while (a != null)
{
temp.Next = a;
a = a.Next;
temp = temp.Next;
}

while (b != null)
{
temp.Next = b;
b = b.Next;
temp = temp.Next;
}
return merged.Next;
}

{
while (fast != null && fast.Next != null)
{
slow = slow.Next;
fast = fast.Next.Next;
}
return slow;
}
#endregion

{
List<int> list = new List<int>();
while (head != null)
{
}
return list;
}

{
StringBuilder sb = new StringBuilder();
sb.AppendLine("<style>");
sb.AppendLine(".node { float:left;width:45px;height:45px;line-height:45px;font-size:21px;text-align:center;border:solid 1px #DD0000; }");
sb.AppendLine(".node_cur { float:left;width:45px;height:45px;line-height:45px;font-size:21px;font-weight:bold;text-align:center;border:solid 1px #FF6701;background-color:#FAFA90; }");
sb.AppendLine(".link { float:left;width:45px;height:45px;line-height:45px;font-size:12px;text-align:center;border:solid 0px #DD0000;white-space:nowrap;word-break:keep-all; }");
sb.AppendLine("</style>");
while (head != null)
{
if (head == cur)
{
sb.AppendLine("<div class='node_cur'>" + head.Data + "</div>");
}
else
{
sb.AppendLine("<div class='node'>" + head.Data + "</div>");
}
{
}
}
return sb.ToString();
}
}
}
``````

``````	public class LinkNode
{
public int Data { get; set; } = 0;
public LinkNode Next { get; set; } = null;