merge sort

Two way merge sort

Two way merge sort mainly uses “ Divide and conquer algorithm ”, Divide and conquer algorithm is to divide a large problem into n A smaller and structurally similar subproblem .

The solutions to these sub problems are similar , After solving these small problems , The result of the merging subproblem , Got it. “ Big ” The solution of the problem .

The main idea of two-way merge sort is “ decompose ” And “ Merger ”

decompose ：

1. Divide an array into two arrays , Sort the two arrays separately .

2. The first step of the cycle , Until it's divided “ Small array ” Contains only one element , Arrays with only one element are ordered by default .

Merger ：

1. Combine two ordered arrays into a large array .

2. Start with the smallest array that contains only one element and merge in pairs . here , The merged array is also ordered .

chart 1. Merge sort process chart 2. Merge two ordered arrays

Illustrate with examples ：

1. The original array in the figure is {2,4,7,5,8,1,3,6}, The number of elements in the array is 8 individual . First of all, will 8 Binary array of elements , After each disassembly ,

The number of elements in the array is the same as that of the original array . Until it is decomposed into an array containing only one element .

2. Merge small arrays in order , The size of the array after each merge is twice that of the upper array . At this point, the elements in the array are arranged in order .

3. Merging two ordered arrays . Pictured 2

  （1）  When merging , There are two pointers to an ordered array A and B The starting element of , Compare the size of the element indicated by the pointer , If A[i] smaller , Will A[i]

Save to array C in , And will i Move backward . Cycle comparison i and j The element referred to .

  （2） When an array A After all the elements of , Array B Pointer in does not point to B At the end of , take B All the remaining elements in are stored in C in .

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 void Merge(int array[], int p, int q, int r);
 5 void MergeSort(int array[], int p, int q);
 6 
 7 int main()
 8 {
    
 9     //int array[7] = {1,3,5,2,4,5,10};
10     int array[8] = {
    5,2,4,7,1,3,2,6};
11     int i = 0;
12 
13     MergeSort(array, 0, 7);
14     //Merge(array, 0, 2, 6);
15 
16     for(i; i < 8; i++)
17         printf("%d ", array[i]);
18     return 0;
19 }
20 
21 // During the merger  p<=q<r 
22 void Merge(int array[], int p, int q, int r)
23 {
    
24     int n1 = q - p + 1;
25     int n2 = r - q;
26 
27     int *L;
28     L = (int*)malloc(sizeof(int)*n1);
29     int *R;
30     R = (int*)malloc(sizeof(int)*n2);
31 
32     int i = 0;
33     int j = 0;
34 
35     for(i; i < n1; i++)
36         L[i] = array[i + p];
37     for(j; j < n2; j++)
38         R[j] = array[j + q  +1];
39 
40     i = j = 0;
41 
42     int k = p;
43 
44     while(i!=n1 && j!= n2)
45     {
    
46         if(L[i] <= R[j])
47             array[k++] = L[i++];
48         else
49             array[k++] = R[j++];
50     }
51 
52     while(i < n1)
53         array[k++] = L[i++];
54     while(j < n2)
55         array[k++] = R[j++];
56 
57     free(L);
58     free(R);
59 }
60 
61 void MergeSort(int array[], int p, int q)
62 {
    
63     if(p < q)
64     {
    
65         int r = (p+q)/2;
66         MergeSort(array, p, r);
67         MergeSort(array, r+1, q);
68         Merge(array,p, r, q);
69     }
70 }