Provides a C implementation of selection, insertion, bubble, merge, and quick sort

Sorts.c

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

// Signature for all sorting functions
typedef void (*SortFunc)(int*,int);

void swap(int* a, int* b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void bubble_sort(int* a, int len)
{
    int i;
    for(i = len-1; i > 0; --i)
    {
        int j;
        for(j = 0; j < i; ++j)
            if(a[j] > a[j+1])
                swap(a + j, a + j + 1);
    }
}

void selection_sort(int* a, int len)
{
    int i;
    for(i = 0; i < len; ++i)
    {
        int j, min = i;
        for(j = i; j < len; ++j)
            if(a[j] < a[min])
                min = j;

        swap(a + i, a + min);
    }
}

void insertion_sort(int* a, int len)
{
    int i;
    for(i = 1; i < len; ++i)
    {
        int j = i;
        int key = a[i];
        while(j > 0 && a[j - 1] > key)
            a[j] = a[j - 1], j--;

        a[j] = key;
    }
}

void merge_arrays(int* a, int start, int mid, int end)
{
    // assume left and right are sorted
    int l = start;
    int r = mid;
    int i = 0;
    int length = end - start + 1;
    int* tmp = (int*)malloc(length*sizeof(int));

    while(l < mid && r <= end)
    {
        if(a[l] < a[r])
            tmp[i++] = a[l++];
         else
            tmp[i++] = a[r++];
    }

    while(l < mid)
        tmp[i++] = a[l++];

    while(r <= end)
        tmp[i++] = a[r++];

    for(i = 0; i < length; ++i)
        a[i + start] = tmp[i];

    free(tmp);
}

void merge_recurse(int* array, int start, int end)
{
    if(start < end)
    {
        int mid = (start + end)/2;

        merge_recurse(array, start, mid);
        merge_recurse(array, mid + 1, end);

        merge_arrays(array, start, mid + 1, end);
    }
}

void merge_sort(int* a, int len)
{
    merge_recurse(a, 0, len-1);
}

int partition(int* a, int start, int end)
{
    // can also pick the median of 3, 5, or 7 elements instead of first element
    // pivot is a[end] by default
    int i = start, j;
    for(j = start; j < end; ++j)
        if(a[j] < a[end])
            swap(a + i, a + j), i++;

    swap(a + i, a + end);

    return i;
}

void quick_recurse(int* a, int start, int end)
{
    // can also fall back to the O(n^2) sorts when the sub-array has < 10/20 elements
    if(start < end)
    {
        int i = partition(a, start, end);

        quick_recurse(a, start, i - 1);
        quick_recurse(a, i + 1, end);
    }
}

void quick_sort(int* a, int len)
{
    quick_recurse(a, 0, len - 1);
}

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

int is_sorted(int* a, int len)
{
    int i = 0;
    for( ; i < len - 1; ++i)
        if(a[i] > a[i + 1])
            return 0;

    return 1;
}

int main()
{
    int array[100] = { 0 };
    const int array_len = sizeof(array) / sizeof(array[0]);

    int i;
    srand(time(0));
    for(i = 0; i < array_len; ++i)
        array[i] = rand();

    SortFunc sortingFunctions[] =
    {
        bubble_sort,
        selection_sort,
        insertion_sort,
        merge_sort,
        quick_sort
    };

    const int numFuncs = sizeof(sortingFunctions) / sizeof(sortingFunctions[0]);

    for(i = 0; i < numFuncs; ++i)
    {
        printf("Sort #%d\n", i+1);
        int* a = (int*)malloc(sizeof(array));
        memcpy(a, array, sizeof(array));
        sortingFunctions[i](a, array_len);
        print_array(a, array_len);
        assert(is_sorted(a, array_len));
        free(a);
    }

    return 0;
}