I. [Topic difficulty]

• Class B

II. [Title No.]

• 1035 insertion and merging (25 points)

III. [Title Description]

• According to the definition of Wikipedia:
  Insertion sorting is an iterative algorithm, which obtains the input data one by one and gradually produces an orderly output sequence. In each iteration, the algorithm takes an element from the input sequence and inserts it into the correct position in the ordered sequence. This iterates until all elements are in order.
  Merge sort performs the following iterative operations: first, the original sequence is regarded as N ordered subsequences containing only one element, and then two adjacent ordered subsequences are merged each iteration until only one ordered sequence is left.
  Given the original sequence and the intermediate sequence generated by a sorting algorithm, please judge which sorting algorithm this algorithm is?

IV. [Title example]

• Input format:
  Enter the positive integer N (≤ 100) given on the first line; The next line gives N integers of the original sequence; The last line gives the intermediate sequence generated by a sorting algorithm. Here, it is assumed that the target sequence of sorting is ascending. Numbers are separated by spaces.

• Output format:
  First, in line 1, output Insertion Sort to indicate Insertion Sort or Merge Sort to indicate Merge Sort; Then output the result sequence of another round of iteration with the sorting algorithm in line 2. The topic ensures that the results of each group of tests are unique. Numbers shall be separated by spaces, and there shall be no extra spaces at the beginning and end of the line.

• Input example 1:
  10
  3 1 2 8 7 5 9 4 6 0
  1 2 3 7 8 5 9 4 6 0

• Output example 1:
  Insertion Sort
  1 2 3 5 7 8 9 4 6 0

• Input example 2:
  10
  3 1 2 8 7 5 9 4 0 6
  1 3 2 8 5 7 4 9 0 6

• Output example 2:
  Merge Sort
  1 2 3 8 4 5 7 9 0 6

V. [problem solving ideas]

• The idea of this problem is not difficult, but the code looks scary. In fact, we only need to write two sorting methods, insert sorting and merge sorting. In each sorting process, we scan whether it is an intermediate sequence. By the way, we store the next sorting result. If it is, print it. If not, continue. Note that, A temporary array should be used to save the input original array. Because the original array has changed after the first insertion and sorting, this array cannot be used for merging and sorting, but the original array should be used

Vi. [final score]

• 25 points

VII. [code implementation]

#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>

int cmp_1035_InsertionAndMerge(int *a,int *b)
{
    return *(int *)a > *(int *)b ? 1 : -1;
}

bool isSame(int* a,int* b,int n)
{
    for(int i = 0;i<n;i++)
    {
        if(a[i] != b[i])
        {
            return false;
        }
    }
    return true;
}

void showNums(int* nums,int n)
{
    for(int i = 0;i<n;i++)
    {
        printf("%d",nums[i]);
        if(i < n - 1)
        {
            printf(" ");
        }
    }
}

bool insertSort(int* nums,int* numsNext,int n)
{
    bool flag = false;
    for(int i = 1;i<n;i++)
    {
        if((i != 1) && isSame(nums,numsNext,n))
        {
            flag = true;
        }
        int key = nums[i];
        int j = i -1;
        while((j >= 0) && (nums[j] > key))
        {
            nums[j + 1] = nums[j];
            j--;
        }
        nums[j+1] = key;
        if(flag == true)
        {
            return true;
        }
    }
    return false;
}

void mergeSort(int* nums,int* numsNext,int n)
{
    bool flag = false;
    int i;
    for(int step = 2;step / 2 <= n;step *=2)
    {
        if((step != 2) && (isSame(nums,numsNext,n)))
        {
            flag = true;
        }
        for(i = 0;i < n / step;i++)
        {
            qsort(nums + i * step,step,sizeof(int),cmp_1035_InsertionAndMerge);
        }
        qsort(nums + i * step, n % step, sizeof(int),cmp_1035_InsertionAndMerge);
        if(flag == true)
        {
            showNums(nums,n);
            return;
        }
    }
}

int main()
{
    int n;
    scanf("%d",&n);
    int* nums = (int *)calloc(n,sizeof(int));
    int* numsNext = (int *)calloc(n,sizeof(int));
    int* temp = (int *)calloc(n,sizeof(int));
    for(int i = 0;i<n;i++)
    {
        scanf("%d",&nums[i]);
        temp[i] = nums[i];
    }
    for(int i = 0;i<n;i++)
    {
        scanf("%d",&numsNext[i]);
    }
    if(insertSort(nums,numsNext,n))
    {
        printf("Insertion Sort\n");
        showNums(nums,n);
    }
    else
    {
        printf("Merge Sort\n");
        mergeSort(temp,numsNext,n);
    }
    return 0;
}

VIII. [submission results]