How to implement the merge sort algorithm in C#

How to implement the merge sort algorithm in C

#Merge sort is a classic sorting algorithm based on the divide and conquer idea, which divides a large problem into multiple small problems, then gradually solve the small problems and merge the results to complete the ranking. The following will introduce how to implement the merge sort algorithm in C# and provide specific code examples.

The basic idea of ​​merge sort is to split the sequence to be sorted into multiple subsequences, sort them separately, and then merge the sorted subsequences into an ordered sequence. The key to this algorithm is to implement the splitting and merging operations of subsequences.

First, we need to write a recursive function to implement the split operation, divide the original sequence into two subsequences, and recursively call the merge sort algorithm to sort the subsequences. The specific code is as follows:

static void MergeSort(int[] array, int left, int right)
{
    if (left < right)
    {
        int middle = (left + right) / 2;
        MergeSort(array, left, middle);
        MergeSort(array, middle + 1, right);
        Merge(array, left, middle, right);
    }
}

Next, we need to write a merge function to merge two ordered subsequences into one ordered sequence. The key to the merge operation is to compare the elements in the two subsequences and put them into an auxiliary array in order of size. The specific code is as follows:

static void Merge(int[] array, int left, int middle, int right)
{
    int[] temp = new int[array.Length];
    int i = left;
    int j = middle + 1;
    int k = left;

    while (i <= middle && j <= right)
    {
        if (array[i] <= array[j])
        {
            temp[k] = array[i];
            i++;
        }
        else
        {
            temp[k] = array[j];
            j++;
        }
        k++;
    }

    while (i <= middle)
    {
        temp[k] = array[i];
        i++;
        k++;
    }

    while (j <= right)
    {
        temp[k] = array[j];
        j++;
        k++;
    }

    for (int l = left; l <= right; l++)
    {
        array[l] = temp[l];
    }
}

Finally, we can sort the array to be sorted by calling the MergeSort function. The specific code is as follows:

static void Main(string[] args)
{
    int[] array = { 5, 3, 8, 4, 2, 1, 9, 7, 6 };
    MergeSort(array, 0, array.Length - 1);

    Console.WriteLine("排序后的数组：");
    for (int i = 0; i < array.Length; i++)
    {
        Console.Write(array[i] + " ");
    }

    Console.ReadLine();
}

The above are the detailed steps to implement the merge sort algorithm in C# and code examples. By recursively splitting the sequence, sorting the subsequences, and merging the results, we can efficiently sort sequences of any size. The time complexity of merge sort is O(nlogn), which is a relatively fast sorting algorithm.

The above is the detailed content of How to implement the merge sort algorithm in C#. For more information, please follow other related articles on the PHP Chinese website!