## Introduction

What I wanted to do here was to provide a public-domain C implementation of the Quicksort algorithm, written from scratch, which anybody could use without licensing liabilities.

## Background

Whenever I was looking for a Quicksort implementation over the Internet, I was always limited to simple, recursive, yet not quite efficient implementation of the algorithm. For a more production-quality code, it seemed that the only stuff I could find was either protected by unknown or restrictive licenses.

This algorithm performs reasonably well with similar performance of the standard *qsort* found in Linux and MacOS X. I tested the code a bit to verify that it was bug-free. However, I should warn people to use this at their own risk, as testing coverage was still limited. I welcome everyone to notify me should they find something wrong with it.

## Using the Code

The code presented below performs a basic Quicksort and after reaching a certain threshold, switches to an insertion sort. This implementation is the in-place version of the algorithm and is done in the following way:

- In the middle of the array, we determine a pivot that we temporarily swap to the end.
- From the beginning to the end of the array, we swap any elements smaller than this pivot to the start, adjacent to other elements that were already moved.
- We swap the pivot next to these smaller elements.
- For both sub-arrays on sides of the pivot, we repeat this process recursively.
- For a sub-array smaller than a certain threshold, the insertion sort algorithm takes over.

So here it is:

#include <limits.h>
#include <stddef.h>
#ifndef INSERTION_SORT_THRESHOLD_SHIFT
# ifdef __APPLE__ & __MACH__
# define INSERTION_SORT_THRESHOLD_SHIFT 0
# else
# define INSERTION_SORT_THRESHOLD_SHIFT 2
# endif
#endif
#define SWAP(A,B,SIZE) \
{ \
register char *a_byte = A; \
register char *b_byte = B; \
register const char *a_end = a_byte + SIZE; \
\
while (a_byte < a_end) \
{ \
register const char swap_byte = *b_byte; \
*b_byte++ = *a_byte; \
*a_byte++ = swap_byte; \
} \
}
#define SWAP_NEXT(A,SIZE) \
register char *a_byte = A; \
register const char *a_end = A + SIZE; \
\
while (a_byte < a_end) \
{ \
register const char swap_byte = *(a_byte + SIZE); \
*(a_byte + SIZE) = *a_byte; \
*a_byte++ = swap_byte; \
}
void quicksort(void *array,
size_t length,
size_t size,
int(*compare)(const void *, const void *))
{
struct stackframe
{
void *left;
void *right;
} stack[CHAR_BIT * sizeof(void *)];
struct stackframe *recursion = stack;
#if INSERTION_SORT_THRESHOLD_SHIFT != 0
const int threshold = size << INSERTION_SORT_THRESHOLD_SHIFT;
#endif
recursion->left = array;
recursion->right = (char *)array + size * (length - 1);
do
{
register char *index = recursion->left;
register char *right = recursion->right;
char *left = index;
register char *store = index;
--recursion;
const size_t middle = (right - left) >> 1;
SWAP(left + middle - middle % size,right,size)
while (index < right)
{
if (compare(right, index) > 0)
{
SWAP(index,store,size)
store += size;
}
index += size;
}
SWAP(right,store,size)
#define RECURSE_LEFT \
if (left < store - size) \
{ \
(++recursion)->left = left; \
recursion->right = store - size; \
}
#define RECURSE_RIGHT \
if (store + size < right) \
{ \
(++recursion)->left = store + size; \
recursion->right = right; \
}
#define INSERTION_SORT_LOOP(LEFT) \
{ \
register char *trail = index - size; \
while (trail >= LEFT && compare(trail, trail + size) > 0) \
{ \
SWAP_NEXT(trail,size) \
trail -= size; \
} \
}
#define INSERTION_SORT_LEFT \
for (index = left + size; index < store; index +=size) \
INSERTION_SORT_LOOP(left)
#define INSERTION_SORT_RIGHT \
for (index = store + (size << 1); index <= right; index +=size) \
INSERTION_SORT_LOOP(store + size)
#if INSERTION_SORT_THRESHOLD_SHIFT == 0
# define SORT_LEFT RECURSE_LEFT
#else
# define SORT_LEFT \
if (store - left <= threshold) \
{ \
INSERTION_SORT_LEFT \
} \
else \
{ \
RECURSE_LEFT \
}
#endif
#if INSERTION_SORT_THRESHOLD_SHIFT == 0
# define SORT_RIGHT RECURSE_RIGHT
#else
# define SORT_RIGHT \
if (right - store <= threshold) \
{ \
INSERTION_SORT_RIGHT \
} \
else \
{ \
RECURSE_RIGHT \
}
#endif
if (store - left < right - store)
{
SORT_RIGHT
SORT_LEFT
continue;
}
SORT_LEFT
SORT_RIGHT
#undef RECURSE_LEFT
#undef RECURSE_RIGHT
#undef INSERTION_SORT_LOOP
#undef INSERTION_SORT_LEFT
#undef INSERTION_SORT_RIGHT
#undef SORT_LEFT
#undef SORT_RIGHT
}
while (recursion >= stack);
}
#undef INSERTION_SORT_THRESHOLD_SHIFT
#undef SWAP
#undef SWAP_NEXT

As someone could expect, the function prototype is the same as the `qsort `

found in the C standard. A comparison function for sorting integers could be the same as the following:

int compare(const void *a, const void *b)
{
return (*(int *)a - *(int *)b);
}

## Points of Interest

As an optimization, rather than performing a real recursion, I kept a global stack to track boundaries for each recursion level.

As explained in various articles, the log_{2} of the highest unsigned value of an integer type is the number of bits needed to store that same integer. Thus, keeping a stack size of `8 * sizeof(void *) `

makes sense. To ensure that at most O(log_{2} N) space is always used, I also recursed into smaller partitions first.

Based on experimental results, I noticed that the insertion-sort was slower on MacOS X, regardless of the array size threshold. While trying to maintain portability, I couldn't help but disable the algorithm for that particular platform.

## History

- 07/23/2012: Initial release to CodeProject.com
- 07/23/2012: Fixed typos, wording, and minor source-code change
- 10/13/2013: Fixed functional issue with pivot calculation