Sorting algorithm—merge sort [with code]

#What is merge sort?

Simply speaking, merge sort is to integrate two ordered sequences together.

Recommended tutorial: PHP video tutorial

How to combine two ordered sequences What about integrating them together?

Then we assume that we now have M = {m1, m2, m3, ...., mx} sequence and N = {n1, n2, n3, ...., ny} sequence, these two sequences are already ordered sequences. First create an empty sequence K = {}, then compare m1 and n1, add m1 < n1, then put m1 into the K sequence, and then M The sequence cursor moves backward, that is, m2 and n1 will be compared next time until all comparisons are completed and filled in sequence K.

Since merge sort is to integrate ordered sequences, doesn’t it mean that unordered sequences cannot be sorted? This condition is too harsh, right?

Merge sort is based on the divide and conquer method, that is, a completely disordered sequence can be divided wirelessly to achieve an ordered sequence. For example: Now there is M={m1, m2, m3, ...., mx}, the M sequence is a completely disordered sequence, then the M sequence can be divided into several small sequences - {m1, m2}, {m3, m4 ｝....{mx-1, mx}; At this time, these sequences are in order, then they can be sorted through the merge operation, so merge sort can also sort unordered sequences, and its speed is second only to quick sort, which belongs to Stable sorting.

How to split the sequence?

The previous question has been mentioned. Merge sort is based on divide and conquer. The embodiment of divide and conquer is reflected in the partition sequence. For example: now there are M ={m1, m2, m3, ...., mx}, the first division: M1 = {m1, m2, ..., m(x 1)/2}, M2 = {m(x 1)/ 2 1, m(x 1)/2 2,...,mx}, after the first division, we get M1 and M2 sequences, and then divide M1 and M2 again, and after dividing several times, we get x/2 x%2 sequences , and then perform the merge operations one by one.

The specific steps of this algorithm:

1. Specify the first pointer left and mid (left points to the first element of sequence 1, right points to sequence 2 The first element)

2. Compare the sizes of left and mid and put the small elements into the newly created space

3. Repeat step 2 until one of the sequences has been traversed

　4. Copy and paste the remaining elements that have not been added to the new space directly into the new space

The core steps of the algorithm:

　1. Use the divide-and-conquer method (recursion) to split the sequence

　2. Compare the sizes of left and mid, and add small elements into the new space

narration Completed, paste the code:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 排序__归并排序
{
    class 归并
    {

        public static int[] arr = { 6, 202, 301, 100, 38, 8, 1 ,-1,1000};
        static void Main(string[] args)
        {
            Sort(arr, 0, arr.Length -1);
            foreach (var item in arr)
            {
                Console.Write(item + "  ");
            }
            Console.ReadKey();
        }

        public static void Sort(int []a,int left,int right)
        {
            if (left >= right) return;
            else
            {
                int mid = (left + right) / 2;                //@1
                Sort(a, left, mid);
                Sort(a, mid + 1, right);
                MergeSort(a, left, mid, right);
            }
        }

        public static void MergeSort(int []a,int left,int mid,int right)
        {
            int[] Arr = new int[right - left + 1];
            int l = left, m = mid +1 , k = 0;           //@2
            while ( m <= right && l <= mid )          //@3
            {
                if (a[l] > a[m]) Arr[k++] = a[m++];
                else Arr[k++] = a[l++];
            }
            while (m < right +1)                           //@4
            {
                Arr[k++] = a[m++];
            }
            while (l < mid +1 )  Arr[k++] = a[l++];        //@4
            for (k = 0, l = left; l < right + 1; k++, l++) a[l] = Arr[k];
        }
    }
}

Code interpretation:

@1: The Sort() function completes the segmentation of the sequence. Each recursion divides the sequence into two halves until it cannot be separated.

@2: l represents the first element of sequence 1, m represents the first element of sequence 2, k represents the number of existing elements in the new array Arr

@3: The first element of sequence 1 Compare with the first element of sequence 2, put the small one into Arr, and move the sequence cursor back until the elements of one of the sequences are compared.

　@4: The comparison process between sequence 1 and sequence 2 , it may appear that sequence 1 has all been added to Arr, but sequence 2 has not, then the remaining uncompared elements will be copied directly into Arr

##Summary:

The above code does not split the array in the true sense. It just makes a logical split. It does not fill the split array into a new array like other codes. Doing so will have a slight impact on speed and memory. Although it is minimal, it is not so good after all. In the merge operation, you need to pay attention to the parameters not crossing the boundary (I thought for a long time why the m above @2 should be equal to mid 1 instead of mid. In fact, the reason is very simple, because Mid belongs to the left sequence, and only belongs to the right sequence starting from mid 1. It is not impossible to change m = mid 1 to m = mid, but the subsequent code also needs to be changed, but there is no need to do one more useless comparison. I really thought about this problem at the time After thinking about it for a long time...), in fact, as long as the logical relationship is clarified, the code can be easily grasped.

The above is the detailed content of Sorting algorithm—merge sort [with code]. For more information, please follow other related articles on the PHP Chinese website!