Timsort.c

#include <stdio.h>

const int THRESHOLD = 32;

int is_odd(int n) {
    return n & 1;
}

int get_fmin(int a, int b) {
    if (a < b) {
        return a;
    }
    return b;
}

int get_floor(int n) {
    return n / 2;
}

void print_array(int array[], int size) {
    printf("[");
    for (int i = 0; i < size; i++) {
        printf("%d", array[i]);
        if (i != size - 1) {
            printf(", ");
        }
    }
    printf("]\n");
}

int get_run_length(int size_of_array) {
    int run_length = size_of_array;
    int remainder = 0;

    while (run_length >= THRESHOLD) {
        if (is_odd(run_length)) {
            remainder = 1;
        }
        run_length = get_floor(run_length / 2);
    }
    return run_length + remainder;
}

void insertion_sort(int array[], int left_index, int right_index) {
    for (int i = left_index + 1; i <= right_index; i++) {
        int temp = array[i];
        int j = i - 1;
        while (j >= left_index && array[j] > temp) {
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = temp;
    }
}

void merge_runs(int array[], int left_index, int middle_index, int right_index) {
    int left_size = middle_index - left_index + 1;
    int right_size = right_index - middle_index;
    int left[left_size];
    int right[right_size];

    for (int i = 0; i < left_size; i++) {
        left[i] = array[left_index + i];
    }
    for (int j = 0; j < right_size; j++) {
        right[j] = array[middle_index + 1 + j];
    }

    int i = 0;
    int j = 0;
    int k = left_index;

    while (i < left_size && j < right_size) {
        if (left[i] <= right[j]) {
            array[k] = left[i];
            i++;
        } else {
            array[k] = right[j];
            j++;
        }
        k++;
    }

    while (i < left_size) {
        array[k] = left[i];
        i++;
        k++;
    }

    while (j < right_size) {
        array[k] = right[j];
        j++;
        k++;
    }
}

void timsort(int array[], int size) {
    int run_length = get_run_length(size);

    for (int i = 0; i < size; i += run_length) {
        insertion_sort(array, i, get_fmin((i + run_length - 1), (size - 1)));
    }

    for (int size_of_run = run_length; size_of_run < size; size_of_run *= 2) {
        for (int left_index = 0; left_index < size; left_index += 2 * size_of_run) {
            int middle_index = left_index + size_of_run - 1;
            int right_index = get_fmin((left_index + 2 * size_of_run - 1), (size - 1));
            merge_runs(array, left_index, middle_index, right_index);
        }
    }
}

int main() {
    int array[] = { 5, 2, -2147483648, 1, 4, 5323, -1, 0, 10, 9, 8, 7, 6, 2147483647, 4, 3, 2 };
    int size = sizeof(array) / sizeof(array[0]);

    printf("Original array:\t");
    print_array(array, size);

    timsort(array, size);

    printf("Sorted array:\t");
    print_array(array, size);
    return 0;
}