Median of 3 Quicksort in C I'm trying to re-implement the C stdlib function qsort using a median of 3 quicksort.

void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*))


This is my first major project in C, and I'd like to know how my style looks and what techniques I might be missing out on. Thanks for the help.

In sort.h, I have

/* returns &gt; 0 if arg1 is greater than arg2, 0 if equal, &lt; 0 if less*/
typedef int (*compare_func)(void *, void *);
/*Median of 3 quicksort Function*/
void quick_sort(void * arr, size_t nitems, size_t size,  compare_func compare);


And in quick_sort.c I have

#include "sort.h"
#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;string.h&gt;    

void swap_mem(void * ptr1, void * ptr2, size_t size){
    /*
     * Swaps the values at the addresses pointed at by ptr1 and ptr2
     */
    void * tmp = malloc(size);
    memcpy(tmp, ptr1, size);
    memcpy(ptr1, ptr2, size);
    memcpy(ptr2, tmp, size);
    free(tmp);
}

void median_of_3(void * arr, size_t start, size_t stop, size_t size, compare_func compare){
    /*
     * Performs median of 3 partitioning on an array starting at start and ending
     * at stop
     */
    int mid;

    /*determine midpoint of array to nearest integer multiple of size*/
    mid = ((start + stop)&gt;&gt;1)/size * size;

    /*sort the 3 item array by comparing middle value to first and last value*/
    if(compare(arr + stop, arr + start) &lt; 0)
        swap_mem(arr + stop, arr + start, size);
    if(compare(arr + mid, arr + start) &lt; 0)
        swap_mem(arr + mid, arr + start, size);
    if(compare(arr + stop, arr + mid) &lt; 0)
        swap_mem(arr + stop, arr + mid, size);

    /*swap the second to last value of arr with the median value*/
    swap_mem(arr + mid, arr + stop - size, size);
}

void quick_sort_aux(void * arr, size_t start, size_t stop, size_t size, compare_func compare){
    /*
     * Recursive median-of-3 quick sort
     */

    /*Base Case 1: 1 item in array (already sorted)*/
    if(start &gt;= stop) return;

    /*Base Case 2: sort 2 or 3 item array*/
    median_of_3(arr, start, stop, size, compare);

    if(stop - start &lt;=2*size) return;

    /*Recursively sort larger arrays*/
    int l_ptr = start;
    int r_ptr = stop - 2*size;

    /*move all values to the proper side of the pivot*/
    while(l_ptr &lt;= r_ptr){
        while(compare(arr + l_ptr, arr + stop - size) &lt; 0 &amp;&amp; l_ptr &lt;= r_ptr)
            l_ptr+=size;
        while(compare(arr + r_ptr, arr + stop - size) &gt;= 0 &amp;&amp; l_ptr &lt;= r_ptr)
            r_ptr-= size;
        if(l_ptr &lt;= r_ptr)
            swap_mem(arr + l_ptr, arr + r_ptr,size);
    }
    /*swap the pivot back into place*/
    swap_mem(arr + l_ptr, arr + stop - size,size);

    /*recursively sort the two halves*/
    quick_sort_aux(arr, start, l_ptr - size, size, compare);
    quick_sort_aux(arr, l_ptr + size, stop, size, compare);
}

void quick_sort(void * arr, size_t nitems, size_t size,  compare_func compare){
    /*
     * wrapper for recursive quick_sort_aux
     */
    quick_sort_aux(arr, 0, size*(nitems-1), size, compare);
}


This is my first time posting to StackExchange. Let me know how I can improve my question.
Your swap_mem will get called O(n log n) times. This makes it worth taking a closer look at for optimization.

One thing you can do is avoid repeated calls to malloc and free and instead preallocate the tmp buffer in the root function call and pass it around or use alloca to allocate the buffer on the stack.

void swap_mem(void * ptr1, void * ptr2, size_t size){
    /*
     * Swaps the values at the addresses pointed at by ptr1 and ptr2
     */
    void * tmp = alloca(size); //will get freed automatically on function exit.
    memcpy(tmp, ptr1, size);
    memcpy(ptr1, ptr2, size);
    memcpy(ptr2, tmp, size);
}