Detailed explanation of merge sorting

​ Merge sort : Divide the element sequence to be sorted into two subsequences of equal length , Sort for each subsequence , And then merge them into a subsequence . The process of merging two subsequences is the merging of two paths .​

• • 
    
• First step ： To apply for space , Make its size the sum of two sorted sequences , This space is used to hold the merged sequence
• The second step ： Set two Pointers , The initial positions are the starting positions of two sorted sequences
• The third step ： Compares the elements pointed to by two pointers , Select relatively small elements to put into the merge space , And move the pointer to the next position Repeat step 3 until a pointer exceeds the end of the sequence
• Step four ： Copy all the remaining elements of another sequence directly to the end of the merge sequence
  • 
    

​ Principle diagram :​

​ Dynamic graphics :​

​ Code implementation :​

Log in and copy

       

        package blog;
        

        
import java.util.Random;
        

        
/**
        
 *  Merge sort 
        
 */
        
public class MergeSort {
        

        
    public static void main(String[] args) {
        
//      int[] num = {12,23,67,13,78,2};
        
//      mergeSort(num,0,num.length-1);
        
//      System.out.println(Arrays.toString(num));
        

        
        int[] arr = new int[1000000];
        
        Random r = new Random();
        
        //  Assign values to array elements 
        
        for (int i = 0; i < arr.length; i++) { //  Generate random number 
        
            int num = r.nextInt();
        
            //  If you don't pass parameters , The range of random numbers is int Range .
        
            arr[i] = num;
        
        }
        

        
        //  Record the time before sorting 
        
        long start = System.currentTimeMillis();
        
        //  Get the time to the current operating system , Expressed in milliseconds  //
        
        //  Sort 
        
        mergeSort(arr, 0, arr.length - 1);
        
        long end = System.currentTimeMillis();
        
        System.out.println(end - start);
        
    }
        

        
    //  Merge sort , Recursive method 
        
    public static void mergeSort(int[] arr, int left, int right) {
        
        //  To write recursion, you must first write the recursion exit 
        
        if (left >= right)
        
            return;
        
        //  Divide the array to be sorted into two parts , Find their midpoint 
        
        int mid = (left + right) / 2; //  This can be written as left + (right-left)/2
        
        //  The advantage of writing this way is to avoid a large number right+left The value of will exceed int Value range of , So there will be no problem , Little details 
        
        //  Row left 
        
        mergeSort(arr, left, mid);
        
        //  Row right 
        
        mergeSort(arr, mid + 1, right);
        
        //  Merger 
        
        merge(arr, left, mid, right);
        
    }
        

        
    //  Sort for each small array split 
        
    public static void merge(int[] arr, int left, int mid, int right) {
        
        //  From the leftmost side of the array left Start arranging , All the way to the far right right, So we need right - left + 1 Space 
        
        int[] temp = new int[right - left + 1];
        
        //  Make i Pointer to the left part 
        
        int i = left;
        
        //  Make j Is the pointer to the right part 
        
        int j = mid + 1;
        
        //  Make k by temp The subscript of a temporary array 
        
        int k = 0;
        
        // Compare the left and right arrays , Put whoever is young in the new array 
        
        while (i <= mid && j <= right)
        
            temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
        
        //  If you do the above sorting i Or less than or equal to mid The words of j It's all lined up , The rest i It must be j Big , So add it directly to temp Just behind 
        
        while (i <= mid)
        
            temp[k++] = arr[i++];
        
        //  Same as above 
        
        while (j <= right)
        
            temp[k++] = arr[j++];
        
        //  An array that will be ordered temp The value of is put into the passed in array arr Where it is , That is, you can put what you never take out into it 
        
        for (int n = 0; n < temp.length; n++) {
        
            arr[left + n] = temp[n];
        
        }
        
    }
        
}
       
       

        
1.
        
2.
        
3.
        
4.
        
5.
        
6.
        
7.
        
8.
        
9.
        
10.
        
11.
        
12.
        
13.
        
14.
        
15.
        
16.
        
17.
        
18.
        
19.
        
20.
        
21.
        
22.
        
23.
        
24.
        
25.
        
26.
        
27.
        
28.
        
29.
        
30.
        
31.
        
32.
        
33.
        
34.
        
35.
        
36.
        
37.
        
38.
        
39.
        
40.
        
41.
        
42.
        
43.
        
44.
        
45.
        
46.
        
47.
        
48.
        
49.
        
50.
        
51.
        
52.
        
53.
        
54.
        
55.
        
56.
        
57.
        
58.
        
59.
        
60.
        
61.
        
62.
        
63.
        
64.
        
65.
        
66.
        
67.
        
68.
        
69.
        
70.
        
71.
        
72.
        
73.
       

​ Time complexity analysis :​

Merge sort comparison takes up memory , But it is an efficient and stable algorithm .

Improved merge sort: when merging, first judge the relationship between the maximum value of the previous sequence and the minimum value of the subsequent sequence, and then determine whether to copy and compare . If the maximum value of the preceding sequence is less than or equal to the minimum value of the following sequence , It shows that the sequence can directly form an ordered sequence without merging , On the contrary, it is necessary . Therefore, when the sequence itself is orderly, the time complexity can be reduced to O(​n​).

TimSort It can be said to be the ultimate optimized version of merge sorting , The main idea is to detect the natural ordered sub segments in the sequence （ If strictly descending sub segment is detected, the flip sequence is ascending sub segment ）. In the best case, both ascending and descending order can reduce the time complexity to O(​n​), It has strong adaptability .

	Best time complexity	Worst time complexity	Average time complexity	Spatial complexity	stability
Traditional merge sort	O(​n​log​n​)	O(​n​log​n​)	O(​n​log​n​)	T(n)	Stable
Improved merge sort [1]	O(​n​)	O(​n​log​n​)	O(​n​log​n​)	T(n)	Stable
TimSort	O(​n​)	O(​n​log​n​)	O(​n​log​n​)	T(n)	Stable

After testing , When sorting 100000 random numbers, the time spent in merging and sorting is 25 Millisecond or so , When sorting onemillion random numbers, it takes about 211 Millisecond or so , When sorting 10 million numbers, it takes about 2.2 second , Merge sort is better than quick sort , Although it is relatively stable , But the efficiency should be lower .