Comparison of different sort algorithms

sorts.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <time.h>

#define SWAP(x,y) do { int tmp = (x); (x) = (y); (y) = tmp; } while(false)

// For heapsort
#define LEFT(x) (2*(x)+1)
#define RIGHT(x) (2*(x)+2)
#define TOP(x) (((x)-1)/2)

void bubble_sort(int *array, int len) {
    for(int i=0;i<len-1;i++) {
        bool changed = false;
        for(int j=0;j<len-1;j++)
            if(array[j] > array[j+1]) {
                SWAP(array[j],array[j+1]);
                changed = true;
            }
        if(!changed)
            break;
    }
}

void selection_sort(int *array, int len) {
    for(int i=0;i<len-1;i++) {
        int min_index = i;
        for(int j=i+1;j<len;j++) {
            if(array[j] < array[min_index])
                min_index = j;
        }
        SWAP(array[min_index], array[i]);
    }
}

void insertion_sort(int *array, int len) {
    for(int i=1;i<len;i++) {
        int elem = array[i];
        int j;
        for(j=i-1;j>=0 && array[j] > elem;j--)
            array[j+1] = array[j];
        array[j+1] = elem;
    }
}

void merge_sort(int *array, int len) {
    if(len < 2)
        return;
    int *first = array;
    int first_len = len/2;
    int *second = array + first_len;
    int second_len = len - first_len;
    merge_sort(first,first_len);
    merge_sort(second,second_len);
    int *new_array = malloc(sizeof(int)*len);
    int i,j;
    for(i=0, j=0;i<first_len && j<second_len;) {
        if(first[i] <= second[j]) {
            new_array[i+j] = first[i];
            i++;
        }
        else {
            new_array[i+j] = second[j];
            j++;
        }
    }
    for(;i<first_len;i++)
        new_array[i+j] = first[i];
    for(;j<second_len;j++)
        new_array[i+j] = second[j];
    for(int k=0;k<len;k++)
        array[k] = new_array[k];
    free(new_array);
}

void quicksort(int *array, int len) {
    if(len < 2)
        return;
    int pivot_pos = 0;
    for(int i=1;i<len;i++) {
        if(array[i] < array[0]) {
            pivot_pos++;
            SWAP(array[i], array[pivot_pos]);
        }
    }
    SWAP(array[0], array[pivot_pos]);
    quicksort(array, pivot_pos);
    quicksort(array + pivot_pos + 1, len - pivot_pos - 1);
}

void push_down_root(int *heap, int len, int root) {
    while(1) {
        int max = root;
        if(LEFT(root) < len && heap[LEFT(root)] > heap[max]) // left node
            max = LEFT(root);
        if(RIGHT(root) < len && heap[RIGHT(root)] > heap[max]) // right node
            max = RIGHT(root);
        if(root == max)
            break;
        SWAP(heap[root], heap[max]);
        root = max;
    }
}

void heapsort(int *array, int len) {
    for(int j=TOP(len-1);j>=0;j--)
        push_down_root(array, len, j);
    for(int i=0;i<len-1;i++) {
        SWAP(array[0], array[len-1-i]);
        push_down_root(array, len-i-1, 0);
    }
}

void print_array(int *array, int len) {
    for(int i=0;i<len;i++)
        printf("%d ",array[i]);
    puts("");
}

struct timespec ts_diff(struct timespec first, struct timespec second) {
    struct timespec diff;
    if(first.tv_nsec < second.tv_nsec) {
        diff.tv_sec = -1;
        diff.tv_nsec = 1000000000;
    }
    else {
        diff.tv_sec = diff.tv_nsec = 0;
    }
    diff.tv_sec += first.tv_sec - second.tv_sec;
    diff.tv_nsec += first.tv_nsec - second.tv_nsec;
    return diff;
}

void test_sort(void (*sort)(int *, int), char* test_name, int *array, int len) {
    struct timespec start, end, diff;
    int *test_array = malloc(len*sizeof(int));
    memcpy(test_array, array, len*sizeof(int));
    puts("--------------------------");
    printf("%s\n", test_name);
    printf("Before: ");
    print_array(test_array, len);
    timespec_get(&start, TIME_UTC);
    sort(test_array, len);
    timespec_get(&end, TIME_UTC);
    printf("After: ");
    print_array(test_array, len);
    diff = ts_diff(end, start);
    printf("Time: ");
    if(diff.tv_sec > 0)
        printf("%lld seconds ", (long long int) diff.tv_sec);
    if(diff.tv_nsec > 0)
        printf("%lld nanosec", (long long int) diff.tv_nsec);
    puts("\n--------------------------");
}

int main(void) {
    int array[] = {4,6,8,1,5,0,3,9,7,2};
    int long_array[] = {3002,9483,2802,8502,6147,2322,2378,1807,5198,7647,704,7956,9505,1413,1078,7683,764,6949,5481,8143,2661,6212,1706,9177,5403,6593,4324,8228,8126,8463,2714,2088,6028,2740,1132,4275,9385,7704,5130,4917,8637,8439,4218,341,3299,5579,9003,4531,4227,2719,3485,7409,5416,9645,9920,8333,3131,3745,5961,8871,5696,4277,7718,8311,8048,3944,512,9104,7697,4921,1848,6263,4759,4851,8856,3674,9115,8031,1601,415,6543,2937,7600,4607,7631,1045,6408,8000,379,8491,5478,5103,3977,1534,5042,8606,7073,6382,1873,6134};
    test_sort(bubble_sort, "Bubble sort", array, 10);
    test_sort(selection_sort, "Selection sort", array, 10);
    test_sort(insertion_sort, "Insertion sort", array, 10);
    test_sort(merge_sort, "Merge sort", array, 10);
    test_sort(quicksort, "Quicksort", array, 10);
    test_sort(heapsort, "Heapsort", array, 10);
    test_sort(bubble_sort, "Bubble sort (Long)", long_array, 100);
    test_sort(selection_sort, "Selection sort (Long)", long_array, 100);
    test_sort(insertion_sort, "Insertion sort (Long)", long_array, 100);
    test_sort(merge_sort, "Merge sort (Long)", long_array, 100);
    test_sort(quicksort, "Quicksort (Long)", long_array, 100);
    test_sort(heapsort, "Heapsort (Long)", long_array, 100);
}