Thực hiện Merge Sort bằng C#

Merge Sort là thuật toán sắp xếp sử dụng phương pháp chia để trị (divide and conquer). Nó chia mảng thành hai phần, sau đó gọi đệ quy cho từng phần. Quá trình tiếp tục cho đến khi mảng được sắp xếp.

Ví dụ

using System;

namespace MergeSortDemo
{
    class Example
    {
        static public void Merge(int[] arr, int p, int q, int r)
        {
            int i, j, k;
            int n1 = q - p + 1;
            int n2 = r - q;
            int[] L = new int[n1];
            int[] R = new int[n2];
            
            for (i = 0; i < n1; i++)
                L[i] = arr[p + i];
            for (j = 0; j < n2; j++)
                R[j] = arr[q + 1 + j];
            
            i = 0; j = 0; k = p;
            
            while (i < n1 && j < n2)
            {
                if (L[i] <= R[j])
                {
                    arr[k] = L[i];
                    i++;
                }
                else
                {
                    arr[k] = R[j];
                    j++;
                }
                k++;
            }
            
            while (i < n1)
            {
                arr[k] = L[i];
                i++; k++;
            }
            
            while (j < n2)
            {
                arr[k] = R[j];
                j++; k++;
            }
        }
        
        static public void MergeSort(int[] arr, int p, int r)
        {
            if (p < r)
            {
                int q = (p + r) / 2;
                MergeSort(arr, p, q);
                MergeSort(arr, q + 1, r);
                Merge(arr, p, q, r);
            }
        }
        
        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("Mảng ban đầu: ");
            for (i = 0; i < n; i++)
                Console.Write(arr[i] + " ");
            
            MergeSort(arr, 0, n - 1);
            
            Console.Write("\nMảng đã sắp xếp: ");
            for (i = 0; i < n; i++)
                Console.Write(arr[i] + " ");
        }
    }
}

Kết quả

Merge Sort
Mảng ban đầu: 76 89 23 1 55 78 99 12 65 100
Mảng đã sắp xếp: 1 12 23 55 65 76 78 89 99 100

Giải thích thuật toán

• MergeSort(): Tính điểm giữa q, đệ quy sắp xếp nửa trái và nửa phải, sau đó gọi Merge() để gộp.
• Merge(): Gộp hai mảng con đã sắp xếp L và R thành một mảng đã sắp xếp.