preface

Merge sort is an efficient sorting algorithm created on merge operations with an efficiency of O(nlogn). It was first proposed in 1945 by John von Neumann. This algorithm is a typical application of divide-and-conquer, and the divide-and-conquer recursion of each layer can be carried out simultaneously. (Quoted from Wikipedia)

The principle of

The above video is from www.youtube.com/watch?v=JSc…

Because of unable to load video in Denver, can be directly click on YouTube (VPN) link, also can to watch my blog links to the original perkyrookie. Making. IO/perkyrookie…

That’s it in a picture

Sample code (non-recursive)

  #include <stdio.h>
  #include <stdlib.h>
  #define MAXSIZE 100 // The maximum value of the array to sort
  ​
  typedef struct// Define a sequence table structure {
      int r[MAXSIZE+1];   // For the array to be sorted, r[0] is used as a sentinel or temporary variable
      int length;         // The maximum length used to store the sequence table
  }SqList;
  ​
  void Merge(int *S, int *T, int low, int m, int high);
  void MergePass(int *S, int *T, int s, int length);
  void MergeSort(SqList *L);
  ​
  int main(a)
  {
      int i;
      int array[] = {39.80.76.41.13.29.50.78.30.11.100.7.41.86};
      SqList L;
      L.length = sizeof(array) /sizeof(array[0]);  // Get the array length
   
      for(i=0; i<L.length; i++) L.r[i+1] =array[i];  // Store the array into a sequential table structure
  ​
      MergeSort(&L);
      
      for(i=0; i<L.length; i++)// Outputs the sorted array
          printf("%d ",L.r[i+1]);
  ​
      return 0;
  }
  ​
  void MergeSort(SqList *L)
  {   
      // Request extra space, because r[0] is the sentinel, so the length is +1
      int* TR = (int *)malloc((L->length+1) *sizeof(int));
      int k = 1;/*k is used to indicate the merge of k elements at a time
      
      while (k < L->length)
      {
          //k is multiplied by 2 each time following 1->2->4->8->16... The principle of the number of binary merging elements
          MergePass(L->r, TR, k, L->length);/* merge */ with auxiliary space first
          k *= 2;
          MergePass(TR, L->r, k, L->length);/* Merge the sorted sequence from the auxiliary space back to the original array */
          k *= 2;
      }
      free(TR);// Free memory
      TR=NULL;
  }
  // Merge two subseries of S with length S into T
  // This code is a bit more difficult to understand, and will be examined later in this article
  void MergePass(int *S, int *T, int s, int length)
  {
      int i = 1;  //r[0] is used as a sentinel or temporary variable
      int j;
      
      while (i <= length2 -*s+1)   //length-i+1(unmerged elements) >= 2s
      {       
          Merge(S, T, i, i+s- 1, i+2*s- 1);
          i= i+2*s;   // The starting point of the next element to increment
      }
      if (i< length-s+1)  // merge the last two sequences
          Merge(S, T, i, i+s- 1, length);
      else
          for (j = i; j <= length; j++)
              T[j] = S[j];
  }
  ​
  // merge sort is the main implementation function
  // Merge ordered S[low..m] and S[m+1..high] into ordered T[low..high]
  void Merge(int *S, int *T, int low, int m, int high)
  {//j increments in the interval [m+1,high], k is used for the subscript increments of the target T, l is the auxiliary variable
      int j, k, l;
      
      for (k = low,j = m+1; low <= m && j <= high; k++)   // Merge the elements in S into T
      {
          if (S[low] < S[j])
              T[k] = S[low++];    T[k] = S[low], low++;
          else
              T[k] = S[j++];      / / in the same way
      }
      
      // if j> low, j> m, j>high, low>m, j>high, low>m
      if (low <= m)
      {
          for (l = 0; l <= m-low; l++)
              T[k+l] = S[low+l];      // Copy the remaining S[low..m] into T
      }
      
      if (j <= high)
      {
          for (l = 0; l <= high-j; l++)
              T[k+l] = S[j+l];        // Copy the remaining S[j..high] into T}}Copy the code

Here’s a detailed analysis of some of the hard-to-understand code:

  void MergePass(int *S, int *T, int s, int length)
  {
      int i = 1;  //r[0] is used as a sentinel or temporary variable
      int j;  
      while (i <= length2 -*s+1)   //length-i+1(unmerged elements) >= 2s
      {       
          Merge(S, T, i, i+s- 1, i+2*s- 1);
          i= i+2*s;   // The starting point of the next element to increment
      }
      if (i< length-s+1)  // merge the last two sequences
          Merge(S, T, i, i+s- 1, length);
      else
          for (j = i; j <= length; j++)
              T[j] = S[j];
  }Copy the code

Lines 5 to 9: pairwise merging of subsequences is implemented here.

  • The judgment condition I <= Length-2 * S +1 can be regarded as Length-I +1 >= 2s, indicating that the uncombined elements are less than 2s and jump out of the cycle, that is, when they are insufficient to form two sub-sequences of length s, jump out of the cycle;

  • The reason why unmerged elements need +1 is explained by an example: the first time we enter the loop, there should be length elements that are unmerged, and I starts at 1, so we need +1.

  • Line 7: The element -1 is passed in because both I +s and I +2s are the starting points of the next sequence, so it is a sequence whose end point is these two values -1.

I < length-s+1 can also be regarded as length-i+1>s

  • If the length of uncombined elements is greater than S, it means that a sequence of length s and a sequence of length less than s can also be formed, namely the last two sequences. In this case, one merging should be performed.

  • Else: If the length of the unmerged element is less than s, there is only one sequence left.

The rest should make sense.



Reprint please state:

Author: The Cricket outside the window

The original link: https://juejin.cn/post/6844903750352683016