C# merge sort

C# Merge sort

using System;  
using System.Collections.Generic;  
using System.Linq;  
using System.Text;  
namespace Sort  
{  
    class MergeSorter  
    {  
        /// <summary>  
        /// 归并排序之归：归并排序入口   
        /// </summary>  
        /// <param name="data">无序数组</param>  
        /// <returns>有序数组</returns>  
         public static int[] Sort(int[] data)  
        {  
            //若data为null，或只剩下1 or 0个元素，返回，不排序  
            if (null == data || data.Length <= 1)  
            {  
                return data;  
            }  
            //取数组中间下标  
            int middle = data.Length >> 1;  
            //初始化临时数组let,right，并定义result作为最终有序数组，若数组元素奇数个，将把多余的那元素空间预留在right临时数组  
            int[] left = new int[middle];  
            int[] right =  new int[data.Length - middle];  
            int[] result = new int[data.Length];  
            for (int i = 0; i < data.Length; i++)  
            {  
                if (i < middle)  
                {  
                    left[i] = data[i];  
                }  
                else  
                {  
                    right[i-middle] = data[i]; //此处i-middle，让我省掉定义一个j，性能有所提高  
                }  
            }  
            left = Sort(left);//递归左数组  
            right = Sort(right);//递归右数组  
            result = Merge(left, right);//开始排序  
            return result;  
        }  
        /// <summary>  
        /// 归并排序之并:排序在这一步  
        /// </summary>  
        /// <param name="a">左数组</param>  
        /// <param name="b">右数组</param>  
        /// <returns>合并左右数组排序后返回</returns>  
         private static int[] Merge(int[] a, int[] b)  
         {  
            //定义结果数组，用来存储最终结果  
            int[] result = new int[a.Length + b.Length];  
            int i = 0, j = 0, k = 0;  
            while (i < a.Length && j < b.Length)  
            {  
                if (a[i] < b[j])//左数组中元素小于右数组中元素  
                {  
                    result[k++] = a[i++];//将小的那个放到结果数组  
                }  
                else//左数组中元素大于右数组中元素  
                {  
                    result[k++] = b[j++];//将小的那个放到结果数组  
                }  
            }  
            while (i < a.Length)//这里其实是还有左元素，但没有右元素   
            {  
                result[k++] = a[i++];  
            }  
            while (j < b.Length)//有右元素，无左元素  
            {  
                result[k++] = b[j++];  
            }  
            return result;//返回结果数组  
        }  
    }  
}

Merge sort:
The merge sort method is to merge two (or more than two) ordered lists into a new ordered list, that is, to The sorted sequence is divided into several subsequences, and each subsequence is ordered. Then merge the ordered subsequences into the overall ordered sequence. This algorithm is a very typical application using the divide and conquer method (Divide and Conquer).

Merge the ordered subsequences to obtain a completely ordered sequence; that is, first make each subsequence orderly, and then make the subsequence segments orderly. If two ordered lists are merged into one ordered list, it is called a 2-way merge.

Suppose we have an unsorted sequence, then first we use the splitting method to divide the sequence into sorted subsequences, and then use the merging method to divide the subsequences one by one. Sequences are merged into sorted sequences. The process of segmentation and merging can be seen in the legend below.

As can be seen from the above figure, we first divide an unsorted sequence into 2 parts from the middle, and then divide the 2 parts into Divide it into 4 parts, and divide it in sequence until it is divided into data one by one, and then merge these data together to make them orderly, keep merging, and finally become an ordered sequence.

How to merge two sorted subsequences into one sorted sequence? You can refer to the method below.

Suppose we have two sorted subsequences.

Sequence A: 1 23 34 65

Sequence B: 2 13 14 87

Then you can merge them into one sequence according to the following steps.

(1) First set a new sequence C[8].
(2) Compare A[0] and B[0], A[0] = 1, B[0] = 2, A[0] (3) Compare A[1] and B[0], A[1] = 23, B[0] = 2, A[1] > B[0], then C[1] = 2
(4) Compare A[1] and B[1], A[1] = 23, B[1] = 13, A[1] > B[1], then C[2] = 13
(5) Comparing A[1] and B[2], A[1] = 23, B[2] = 14, A[1] > B[2], then C[3] = 14
( 6) Comparing A[1] and B[3], A[1] = 23, B[3] = 87, A[1] (7 ) Comparing A[2] and B[3], A[2] = 34, B[3] = 87, A[2] (8) Comparing A[3] and B[3], A[3] = 65, B[3] = 87, A[3] (9) Finally Copy B[3] to C, then C[7] = 87. The merge is completed.

C# Shift operation (left shift and right shift)

Merge sort, The time complexity is O(nlogn).

The efficiency of merge sorting is relatively high. Assume the length of the sequence is N. It takes logN steps to separate the sequence into decimal sequences. Each step is a process of merging ordered sequences. The time complexity can be recorded as O(N), so the total is O(N*logN). Because merge sort operates on adjacent data every time, several sorting methods of merge sort (quick sort, merge sort, Hill sort, heap sort) in O(N*logN) are also relatively efficient. .

The above is the content of C# merge sorting. For more related content, please pay attention to the PHP Chinese website (www.php.cn)!