Combine insertion sort with quick sort function relationship

Question

A hybrid sorting:
array A's element index from int p to int r, we initially sort A[] by quick sort method, the pivot is initially placed at the end of the array, then recursively call quick sort, however as the number of elements in the array is smaller than t, then we stop call quick sort and sort the rest of element by insertion sort, the hybrid function should return the times of calling insertion sort only. The main function print out the times of calling insertion sort.

I write this code several times yet always such a mess on the relationship of functions, a huge amount of bug information that I can't diagnose. and I don't know why it is a faster implementation in practice than combining with randomized_quick_sort. Thanks

#include<stdio.h>
#include<stdlib.h>
// hybrid quick sort
int hybridsort(int A[], int p, int q, int t);

int  main() {
  int n = 9, t = 3;
  int A[9] = {1, 8, 6, 3, 2, 7, 4, 9, 10};

  for(int i = 0; i < 9; i++)printf(" %d", A[i]);
  printf("\n");

  int res = hybridsort(A, 0, n - 1, t);// rest
  printf("No. of calls = %d\n",res);

  for(int i = 0; i< 9; i++)printf("%d", A[i]);
  printf("\n");

  return 0;
}
int hybridsort(int A[], int p, int r, int t){
  int n, count;
  count = 0;
  int i, j, key;
  n = p - r + 1;
  // if No.elements < t, # of insertion sort gets called
  if(n >= t && p > r ){
      quicksort(A, p, r);
    }
    else{
      // insertionsort
      count = count + 1;
      for(j = 1; j < 6; j++){
      key = A[j];
      i = j - 1;
      while(i > -1 && A[i] > key){
      A[i + 1] = A[i];
      i = i - 1;
    }
    A[i + 1] = key;
   }

 }
}

return count;
}
void quicksort(int A[], int p, int r){
  int q ;
  if(p < r){

    q = partition(A, p,r);
    quicksort(A, p, q - 1);
    quicksort(A, q + 1, r);
  }
}

int partition(int A[], int p, int r){
  int x, i, j, tmp;
  x = A[r];//pivot
  i = p - 1;
  for(j = p; j < r; j++){
    if(A[j] <= x){
      i += 1;
      tmp = A[i];
      A[i] = A[j];
      A[j] = tmp;
    }

  }
  tmp = A[i + 1];
  A[i + 1] = A[r];
  A[r] = tmp;
  return i + 1 ;// pivot index position after sorting

}

Answer 1

Example hybrid quick + insertion sort. The main program would call QuickSort(), which will call InsertionSort for sub-array sizes <= 32.

void InsertionSort(int a[], size_t lo, size_t hi)
{
size_t i = lo+1;
size_t j;
int t;
    while(i <= hi){
        t = a[i];
        j = i;
        while((j > lo) && a[j-1] > t){
            a[j] = a[j-1];
            j -= 1;
        }
    a[j] = t;
    i += 1;
    }
}

void QuickSort(int a[], size_t lo, size_t hi)
{
    if(lo >= hi)
        return;
    if((hi-lo) < 32){
        InsertionSort(a, lo, hi);
        return;
    }
    int pivot = a[lo + (hi - lo) / 2];
    int t;
    size_t i = lo - 1;
    size_t j = hi + 1;
    while(1)
    {
        while (a[++i] < pivot);
        while (a[--j] > pivot);
        if (i >= j)
            break;
        t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    QuickSort(a, lo, j);
    QuickSort(a, j + 1, hi);
}