c++ - 混合合并排序和插入排序

Question

我正在尝试实现合并排序和插入排序的混合。当子数组大小低于阈值时，它应该切换到插入排序。然而，我尝试了一堆不同长度和不同阈值数量的数组，大多数时候没有任何明显的差异，除了 2-3 个较小的比较。有人告诉我，为较小的数组切换到插入排序会有很大帮助。

我做错了吗？

#include <iostream>


int comparisons = 0;
int swaps = 0;

void mergesort(int x[], int l, int r);
void insertionSort(int x[],int start, int end);

int main() {
  int x[] = {9,5,1,4,3,10,29,69,5,9,11,19,21,69,0,2,3,4,5,11,111,96,25,32,21,2,12,3,52,55,23,32,15,15,14,13,9,5,1,4,3,10,29,69,5,9,11,19,21,69,0,2,3,4,5,11,111,96,25,32,21,2,12,3,52,55,23,32,15,15,14,13,};

  // insertionSort(x,10);
  int sizeX= sizeof(x)/sizeof(x[0]) ;
  mergesort(x, 0, sizeX-1);

  for(int i =0;i<sizeX;i++){
    std::cout << x[i] << " ";
  }
  // std::cout << "\nSWAPS: " << swaps;
  std::cout << "\nCOMPARISONS: " << comparisons;
}


void insertionSort(int arr[], int start,int end)
{
    int i, key, j;
    for (i = start +1 ; i < end; i++)
    {
        key = arr[i];
        j = i - 1;
 
        /* Move elements of arr[0..i-1], that are
        greater than key, to one position ahead
        of their current position */
        while (j >= 0 && arr[j] > key)
        {
            comparisons++;

            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

void insertionSort2(int x[],int start, int end){
  for(int i =start; i < end;i++){
    for (int j= i; j!= 0;j--){
      comparisons++;

      if(x[j] < x[j-1]){
        int temp = x[j-1];
        x[j-1] = x[j];
        x[j] = temp;
        swaps++;
      }
      else{
        break;
      }
    }
  }
}


void mergesort(int x[], int l, int r) {
  if (l >= r)
    return;

  int mid = (l + r) / 2;

  if(r - l  < 3){
    insertionSort(x, l,r+1);
  }else{
    mergesort(x, l, mid);
    mergesort(x, mid + 1, r);

    int i = l; 
    int j = mid + 1; 
    int k = 0; 

    int tmp[r - l + 1];

    while (i <= mid && j <= r) {
      comparisons++;
      if (x[i] >= x[j]) {
        tmp[k] = x[j];
        j++;
      } else {
        tmp[k] = x[i];
        i++;
      }
      swaps++;
      k++;
    }

    while (i <= mid) {
      tmp[k] = x[i];
      i++;
      k++;
    }

    while (j <= r) {
      tmp[k] = x[j];
      j++;
      k++;
    }

    for (i = 0; i < k; i++) x[l + i] = tmp[i];
  }
}

标签： c++algorithmsortingmergesortinsertion-sort