วิธีทำ Merge Sort ใน C#

ภาพรวม

Merge Sort เป็นอัลกอริทึมการจัดเรียงแบบ Divide and Conquer (แบ่งและเอาชนะ) โดยแบ่งอาร์เรย์ออกเป็นสองส่วนครึ่ง แล้วเรียกตัวเองซ้ำ (recursive) จนเหลืออาร์เรย์ขนาด 1 จากนั้นรวม (merge) อาร์เรย์ย่อยที่จัดเรียงแล้วกลับเข้าด้วยกัน Merge Sort มีความซับซ้อน O(n log n) ในทุกกรณี และเป็น Stable Sort (รักษาลำดับของค่าเท่ากันไว้)

ตัวอย่างโปรแกรม Merge Sort

using System;

namespace MergeSortDemo
{
    class Example
    {
        // รวมอาร์เรย์ย่อยสองชุดที่จัดเรียงแล้ว
        static public void Merge(int[] arr, int left, int mid, int right)
        {
            int i, j, k;
            int n1 = mid - left + 1; // ขนาดอาร์เรย์ซ้าย
            int n2 = right - mid;    // ขนาดอาร์เรย์ขวา
            
            // สร้างอาร์เรย์ชั่วคราว
            int[] L = new int[n1];
            int[] R = new int[n2];
            
            // คัดลอกข้อมูล
            for (i = 0; i < n1; i++)
                L[i] = arr[left + i];
            for (j = 0; j < n2; j++)
                R[j] = arr[mid + 1 + j];
            
            // รวมกลับเข้าสู่อาร์เรย์หลัก
            i = 0; j = 0; k = left;
            
            while (i < n1 && j < n2)
            {
                if (L[i] <= R[j])  // <= ทำให้ Stable
                    arr[k++] = L[i++];
                else
                    arr[k++] = R[j++];
            }
            
            // คัดลอกเศษที่เหลือ
            while (i < n1)
                arr[k++] = L[i++];
            while (j < n2)
                arr[k++] = R[j++];
        }
        
        // ฟังก์ชัน Merge Sort หลัก
        static public void MergeSort(int[] arr, int left, int right)
        {
            if (left < right)
            {
                int mid = (left + right) / 2;
                MergeSort(arr, left, mid);       // จัดเรียงครึ่งซ้าย
                MergeSort(arr, mid + 1, right);  // จัดเรียงครึ่งขวา
                Merge(arr, left, mid, right);    // รวม
            }
        }
        
        static void Main(string[] args)
        {
            int[] arr = { 76, 89, 23, 1, 55, 78, 99, 12, 65, 100 };
            int n = 10, i;
            
            Console.WriteLine("Merge Sort");
            Console.Write("อาร์เรย์เริ่มต้น: ");
            for (i = 0; i < n; i++)
                Console.Write(arr[i] + " ");
            
            MergeSort(arr, 0, n - 1);
            
            Console.Write("\nอาร์เรย์ที่จัดเรียงแล้ว: ");
            for (i = 0; i < n; i++)
                Console.Write(arr[i] + " ");
        }
    }
}

ผลลัพธ์

Merge Sort
อาร์เรย์เริ่มต้น: 76 89 23 1 55 78 99 12 65 100
อาร์เรย์ที่จัดเรียงแล้ว: 1 12 23 55 65 76 78 89 99 100

การทำงานแบบทีละขั้นตอน

1. การแบ่ง (Divide)

if (left < right)
{
    int mid = (left + right) / 2;
    MergeSort(arr, left, mid);       // ซ้าย
    MergeSort(arr, mid + 1, right);  // ขวา
    Merge(arr, left, mid, right);    // รวม
}

อาร์เรย์ถูกแบ่งซ้ำๆ จนเหลือขนาด 1 (Base case)

2. การรวม (Merge/Conquer)

int i = 0, j = 0, k = left;
while (i < n1 && j < n2)
{
    if (L[i] <= R[j])  // สำคัญ: ใช้ <= เพื่อความเสถียร (Stable)
        arr[k++] = L[i++];
    else
        arr[k++] = R[j++];
}
// คัดลอกเศษเหลือ
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];

ความซับซ้อน (Complexity)

ข้อสังเกตสำคัญ

• Stable Sort: รักษาลำดับสัมพัทธ์ของค่าเท่ากัน (สำคัญสำหรับการจัดเรียงข้อมูลหลายคีย์)
• ต้องการพื้นที่ O(n) สำหรับอาร์เรย์ชั่วคราว - ไม่ใช่ in-place
• เหมาะสำหรับ Linked List (ไม่ต้องการ random access)
• ใช้ใน Array.Sort() ของ .NET สำหรับอาร์เรย์ขนาดใหญ่ (ร่วมกับ Introsort)
• Parallel Merge Sort สามารถทำได้ง่ายเพราะแต่ละครึ่งอิสระต่อกัน

การประยุกต์: Merge Sort แบบ Iterative (Bottom-up)

สำหรับหลีกเลี่ยง recursion stack overflow สามารถเขียนแบบ iterative ได้:

public static void MergeSortIterative(int[] arr)
{
    int n = arr.Length;
    for (int size = 1; size < n; size *= 2)
    {
        for (int left = 0; left < n - 1; left += 2 * size)
        {
            int mid = Math.Min(left + size - 1, n - 1);
            int right = Math.Min(left + 2 * size - 1, n - 1);
            Merge(arr, left, mid, right);
        }
    }
}