在 .NET 9 平臺下，我們對兩種經典的排序算法 MergeSortTest（歸并排序）和 QuickSortTest（快速排序）進行了性能基準測試（Benchmark），以評估它們在不同數據規模下的執行效率、內存分配及垃圾回收行為。

測試使用了 BenchmarkDotNet 工具，確保結果具有高度可重復性和統計意義。

• Datadog.Trace.BenchmarkDotNet

🧪 測試環境

• 運行時（Runtime）：.NET 9.0.6 (X64 RyuJIT AVX2)
• 操作系統：Windows 11 24H2（開發預覽版）
• SDK 版本：.NET SDK 9.0.301
• 測試工具：BenchmarkDotNet v0.15.2
• 測試參數：
  • 數據量 N = 100, 1000, 10000（分別模擬小、中、大數據集）

項目準備

創建項目

使用 .net cli 創建控制臺項目，執行如下命令：

dotnet new console -n SortTest
cd SortTest# 安裝 nuget 包 Datadog.Trace.BenchmarkDotNet
dotnet add package Datadog.Trace.BenchmarkDotNet

控制臺項目 SortTest.csproj 信息如下：

<Project Sdk="Microsoft.NET.Sdk"><PropertyGroup><OutputType>Exe</OutputType><TargetFramework>net9.0</TargetFramework><ImplicitUsings>enable</ImplicitUsings><Nullable>enable</Nullable><PublishAot>true</PublishAot><InvariantGlobalization>true</InvariantGlobalization></PropertyGroup><ItemGroup><PackageReference Include="Datadog.Trace.BenchmarkDotNet" Version="2.61.0" /></ItemGroup></Project>

排序算法實現

• 歸并排序

// =============================
// 排序算法實現：歸并排序
// =============================namespace SortTest;public class MergeSort
{public static void Sort(int[] array){if (array.Length <= 1) return;int mid = array.Length / 2;int[] left = array[..mid];int[] right = array[mid..];Sort(left);Sort(right);Merge(array, left, right);}private static void Merge(int[] result, int[] left, int[] right){int i = 0, j = 0, k = 0;while (i < left.Length && j < right.Length){if (left[i] <= right[j])result[k++] = left[i++];elseresult[k++] = right[j++];}while (i < left.Length)result[k++] = left[i++];while (j < right.Length)result[k++] = right[j++];}
}

• 快速排序

// =============================
// 排序算法實現：快速排序
// =============================namespace SortTest;public class QuickSort
{public static void Sort(int[] array, int low, int high){if (low < high){int pivotIndex = Partition(array, low, high);Sort(array, low, pivotIndex - 1);Sort(array, pivotIndex + 1, high);}}private static int Partition(int[] array, int low, int high){int pivot = array[high];int i = low - 1;for (int j = low; j < high; j++){if (array[j] <= pivot){i++;Swap(array, i, j);}}Swap(array, i + 1, high);return i + 1;}private static void Swap(int[] array, int i, int j){if (i != j){int temp = array[i];array[i] = array[j];array[j] = temp;}}
}

添加測試基準

• Benchmark 測試類

// =============================
// Benchmark 測試類
// =============================using BenchmarkDotNet.Attributes;
using Datadog.Trace.BenchmarkDotNet;namespace SortTest;[DatadogDiagnoser]
[MemoryDiagnoser]
public class SortingBenchmark
{private int[] data = [];[Params(100, 1000, 10000)] // 不同數據規模public int N;[GlobalSetup]public void Setup(){var random = new Random(42); // 固定種子以保證重復性data = Enumerable.Range(0, N).Select(_ => random.Next(0, N)).ToArray();}[Benchmark]public void MergeSortTest(){var copy = (int[])data.Clone();MergeSort.Sort(copy);}[Benchmark]public void QuickSortTest(){var copy = (int[])data.Clone();QuickSort.Sort(copy, 0, copy.Length - 1);}
}

使用基準測試

在 Program.cs 添加如下代碼：

using BenchmarkDotNet.Configs;
using BenchmarkDotNet.Running;
using Datadog.Trace.BenchmarkDotNet;namespace SortTest;internal class Program
{static void Main(string[] args){Console.WriteLine("Hello, SortingBenchmark!");var config = DefaultConfig.Instance.WithDatadog();BenchmarkRunner.Run<SortingBenchmark>(config);}
}

啟動項目基準測試，使用 pwsh 執行如下命令：

dotnet run -c Release

下面這些文本信息是使用 BenchmarkDotNet 工具對兩種排序算法（MergeSortTest 和 QuickSortTest）進行性能測試后生成的報告。

---

BenchmarkDotNet v0.15.2, Windows 11 (10.0.26100.4484/24H2/2024Update/HudsonValley)
Unknown processor
.NET SDK 9.0.301[Host]     : .NET 9.0.6 (9.0.625.26613), X64 AOT AVX2DefaultJob : .NET 9.0.6 (9.0.625.26613), X64 RyuJIT AVX2

Method	N	Mean	Error	StdDev	Gen0	Gen1	Allocated
MergeSortTest	100	4.508 μs	0.0857 μs	0.1863 μs	5.3635	-	8424 B
QuickSortTest	100	1.249 μs	0.0248 μs	0.0331 μs	0.2689	-	424 B
MergeSortTest	1000	79.005 μs	1.5793 μs	2.1083 μs	61.4014	-	96328 B
QuickSortTest	1000	39.192 μs	0.6847 μs	0.6404 μs	2.5024	-	4024 B
MergeSortTest	10000	1,073.318 μs	20.7670 μs	26.2637 μs	539.0625	128.9063	1112040 B
QuickSortTest	10000	600.722 μs	7.9013 μs	6.5980 μs	24.4141	-	40024 B

---

以下是關鍵內容的通俗解釋：

📊 測試目標

對兩種排序算法在不同數據量下的性能進行對比分析，包括：

• 執行時間（Mean）
• 內存分配（Allocated）
• 垃圾回收情況（Gen0, Gen1）

測試分別在以下數據規模下運行：

• N = 100
• N = 1000
• N = 10000

---

🧪 性能對比結果

方法	數據量 (N)	平均耗時	內存分配	GC 次數 (Gen0)
MergeSortTest	100	4.508 μs	8424 B	5.3635
QuickSortTest	100	1.249 μs	424 B	0.2689
MergeSortTest	1000	79.005 μs	96328 B	61.4014
QuickSortTest	1000	39.192 μs	4024 B	2.5024
MergeSortTest	10000	1073.318 μs	1112040 B	539.0625
QuickSortTest	10000	600.722 μs	40024 B	24.4141

? 結論：

• QuickSortTest 的平均耗時和內存占用都明顯低于 MergeSortTest
• 隨著數據量增加，兩者的差距也越來越大
• QuickSortTest 在性能和資源消耗方面更優

---

?? 警告與提示

📌 多峰分布警告（Multimodal Distribution）

• MergeSortTest 的部分測試結果顯示為多峰分布（mValue = 3.23），說明其運行時間波動較大，可能受外部因素影響。

📌 異常值（Outliers）

• 報告中指出某些測試存在異常值并已被剔除：
  • MergeSortTest: 移除了 4 個異常值
  • QuickSortTest: 不同數據規模下檢測到多個異常值并移除

---

📋 統計指標含義簡述

指標名	含義解釋
Mean	平均執行時間
Error	置信區間的一半（99.9% 置信度）
StdDev	標準差，反映數據波動程度
Gen0 / Gen1	垃圾回收次數（代數0/1）
Allocated	單次操作分配的內存大小
Median	中位數，排除極端值后的中間值
Min / Max	最小值和最大值

---

🖼? 直方圖（Histogram）

每組測試后都有一個簡單的直方圖，用字符 @ 表示不同時間段內執行次數的分布，幫助可視化執行時間的集中趨勢。

---

📈 小結

• QuickSortTest 在所有測試中表現更優
  • 更快的執行速度
  • 更少的內存分配
  • 更低的垃圾回收壓力
• MergeSortTest 性能較差且波動較大
  • 特別是在大數據量（N=10000）時表現不佳
  • 存在較多異常值，穩定性不如 QuickSort

---

如果你希望進一步優化 MergeSort 或想了解為何它表現不佳，可以結合代碼邏輯、遞歸深度、內存使用等因素進行深入分析。