quick_tuned.h

// Based on http://cphstl.dk/Paper/Quicksort/Report-2014-1/doc.pdf

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

void swap(int *a, int *b);
int median_of_three_of_median_of_three(int array[], int low, int high);
void insertionSort(int array[], int n);

int partition_quick_tuned(int array[], int low, int high) {
  int pivot = median_of_three_of_median_of_three(array, low, high);

  int p = low - 1;
  int q = low;
  while(q < high){
    int x = array[q];
    bool smaller = x < pivot;
    p += smaller;
    int delta = smaller * (q - p);
    int s = p + delta;
    int t = q - delta;
    array[s] = array[p];
    array[t] = x;
    q++;
  }
  p++;
  swap(&array[p], &array[high]);
  return p;
}

void sort_quick_tuned(int array[], int low, int high) {
  if (low < high) {
    if (high - low > 16) {
      int pi = partition_quick_tuned(array, low, high);
      sort_quick_tuned(array, low, pi - 1);
      sort_quick_tuned(array, pi + 1, high);
    } else {
      insertionSort(array + low, high - low + 1);
    }
  }
}