A brief discussion of 2 way insertion sort algorithm and its simple implementation

The two-way insertion sort algorithm adds an auxiliary array on the basis of the direct insertion sort algorithm, which aims to reduce the number of moves in the sorting process and needs to increase the auxiliary space of n records.

The difficulty may lie in the consideration of the remainder, you can think of the auxiliary array as a ring space, so that you can better understand the position of the maximum and minimum values in the auxiliary space.

The whole idea of the algorithm is still very simple, directly posted to run code, comments or very clear, you directly see ok

C language implementation example

  #include <stdio.h> 
  #include <stdlib.h> 
   
  void insert_sort(int *arr, int *temp, int n) 
  { 
    int i, first, final, k; 
   
    first = final = 0; 
    temp[0] = arr[0]; 
   
    for (i = 1; i < n; i ++) { 
      if (arr[i] < temp[first]) { //The element to be inserted is smaller than the smallest element
        first = (first - 1 + n) % n; 
        temp[first] = arr[i]; 
      } else if (arr[i] > temp[final]) { //The element to be inserted is larger than the largest element
        final = (final + 1 + n) % n; 
        temp[final] = arr[i]; 
      } else { //Insert elements larger than minimum and larger than maximum
        k = (final + 1 + n) % n; 
        while (temp[((k - 1) + n) % n] > arr[i]) { 
          temp[(k + n) % n] =temp[(k - 1 + n) % n]; 
          k = (k - 1 + n) % n; 
        } 
        temp[(k + n) % n] = arr[i]; 
        final = (fianl + 1 + n) % n; 
      } 
    } 
   
    //Copies the sort records into the original order table
    for (k = 0; k < n; k ++) { 
      arr[k] = temp[(first + k) % n]; 
    } 
  } 
   
  int main(void) 
  { 
    int i, n, *arr, *temp; 
   
    while (scanf("%d", &n) != EOF) { 
      arr = (int *)malloc(sizeof(arr) * n); 
      temp = (int *)malloc(sizeof(temp) * n); 
   
      for (i = 0; i < n; i ++) 
        scanf("%d", &arr[i]); 
   
      insert_sort(arr, temp, n); 
   
      for (i = 0; i < n; i ++) 
        printf("%d ", arr[i]); 
      printf("n"); 
      free(arr); 
      free(temp); 
    } 
   
    return 0; 
  } 

   
Enclosed is the C++ writing method:

#include<iostream>
using namespace std;
#define MAX 20
void PrintArray(int a[],int len){
 for(int i=0;i<len;i++)
 cout<<a[i]<<" ";
 cout<<endl;
}
void BinInsertSort(int a[],int len){
 int *d=(int *)malloc(len*sizeof(len));
 for(int i=0;i<len;i++)
 d[i]=0;
 int first=0,final=0;
 d[0]=a[0];
 for(int i=1;i<len;i++){
 if(a[i]<=d[first]){
  first=(first-1+len)%len;
  d[first]=a[i];
 }
 else if(a[i]>=d[final]){
  final=final+1;
  d[final]=a[i];
 }
 else{
  int j=final++;
  while(a[i]<d[j]){
  d[(j+1)%len]=d[j];
  j=(j-1+len)%len;
  }
  d[j+1]=a[i];
 }
 }
 cout<<" The sorting result in the auxiliary array is: ";
 PrintArray(d,len);
}
int main(){
 int a[MAX],len;
 cout<<" Please enter the number of elements to be sorted: ";
 cin>>len;
 cout<<" Please enter the element to be sorted: ";
 for(int i=0;i<len;i++)
 cin>>a[i];
 BinInsertSort(a,len);
 system("pause");
 return 0;
}