针对算法导论第二章的 Problem 2-4的C#实现：
public static Int32 MergeSort(Int32[] InputArray)
{
// Divide: Divide the n-element sequence to be sorted into two subsequences of n/2 elements each.
Int32 Length = InputArray.Length;
if (Length < 2) return 0;
Int32 invCnt = 0; // Inversion number
Int32 middle = Length / 2;
Int32 lIdx = 0;
Int32[] lArray = new Int32[middle];
Array.Copy(InputArray, 0, lArray, 0, lArray.Length);
Int32 rIdx = 0;
Int32[] rArray = new Int32[Length - middle];
Array.Copy(InputArray, middle, rArray, 0, rArray.Length);
// Conquer: Sort the two subsequences recursively using merge sort.
if (lArray.Length >= 2) invCnt += MergeSort(lArray);
if (rArray.Length >= 2) invCnt += MergeSort(rArray);
// Combine: Merge the two sorted subsequences to produce the sorted answer.
lIdx = rIdx = 0;
Int32 mergeIdx = 0;
while(mergeIdx < InputArray.Length && lIdx < lArray.Length && rIdx < rArray.Length )
{
if (lArray[lIdx] <= rArray[rIdx]) InputArray[mergeIdx++] = lArray[lIdx++];
else
{
invCnt += lArray.Length - lIdx;
InputArray[mergeIdx++] = rArray[rIdx++];
}
}
while(lIdx < lArray.Length) InputArray[mergeIdx++] = lArray[lIdx++];
while(rIdx < rArray.Length) InputArray[mergeIdx++] = rArray[rIdx++];
return invCnt;
}
public static Int32 MergeSort(Int32[] InputArray){
// Divide: Divide the n-element sequence to be sorted into two subsequences of n/2 elements each. Int32 Length = InputArray.Length; if (Length < 2) return 0; Int32 invCnt = 0; // Inversion number Int32 middle = Length / 2; Int32 lIdx = 0; Int32[] lArray = new Int32[middle]; Array.Copy(InputArray, 0, lArray, 0, lArray.Length); Int32 rIdx = 0; Int32[] rArray = new Int32[Length - middle]; Array.Copy(InputArray, middle, rArray, 0, rArray.Length); // Conquer: Sort the two subsequences recursively using merge sort. if (lArray.Length >= 2) invCnt += MergeSort(lArray); if (rArray.Length >= 2) invCnt += MergeSort(rArray); // Combine: Merge the two sorted subsequences to produce the sorted answer. lIdx = rIdx = 0; Int32 mergeIdx = 0; while(mergeIdx < InputArray.Length && lIdx < lArray.Length && rIdx < rArray.Length ) {
if (lArray[lIdx] <= rArray[rIdx]) InputArray[mergeIdx++] = lArray[lIdx++]; else { invCnt += lArray.Length - lIdx; InputArray[mergeIdx++] = rArray[rIdx++]; } } while(lIdx < lArray.Length) InputArray[mergeIdx++] = lArray[lIdx++]; while(rIdx < rArray.Length) InputArray[mergeIdx++] = rArray[rIdx++]; return invCnt;}