# Quick Sort in C

I'd like to know if there's any issues with this implementation of qsort_r (which is not available in all implementations, so I'm trying to provide one that allows to compare values in a dynamic environment) and whether it could be improved upon.

typedef int32_t compare_fn(void *data, const void *val1, const void *val2);

void memswap(void *mem1, void *mem2, size_t size)
{
uint8_t buffer[size];

memcpy(buffer, mem1, size);
memcpy(mem1, mem2, size);
memcpy(mem2, buffer, size);
}

void qsort_r(void *mem_low, void *mem_hi, size_t size, compare_fn compare, void *data)
{
if (mem_low >= mem_hi || mem_hi < mem_low)
{
return;
}

uint8_t *mem_i = mem_low;
uint8_t *mem_j = mem_low;

while (mem_j < mem_hi)
{
if (compare(data, mem_j, mem_hi) < 0)
{
memswap(mem_i, mem_j, size);
mem_i += size;
}

mem_j += size;
}

memswap(mem_i, mem_hi, size);

qsort_r(mem_low, mem_i - size, size, compare, data);
qsort_r(mem_i + size, mem_hi, size, compare, data);
}


1. Pointer-arithmetic on void* is an error in standard c. Yes, gcc/clang have an extension assuming that sizeof(void) == 1. Ramp up your warning-level and specify the standard.

2. That's an interesting method to swap two blocks of memory.

Using a variable length array invites undefined behavior though, as the amount of stack requested is pretty much unbounded.

Anyway, it would probably be a good idea to implement it directly, without such a buffer.

void memswap(void* a, void* b, size_t n) {
unsigned char *c = a, *d = b;
while (n--) {
unsigned char x = *c;
*c++ = *d;
*d++ = x;
}
}

3. I somewhat expected all the elements to be between mem_low and mem_hi. You seem to have an element at mem_hi.
At least if you sort a null terminated string, it just sorts the terminator too.

Did you try to run your code? See it break a basic test-case live on coliru.

• I had tried it on an integer array of 10k elements, but it hid a nasty bug. My pivot cannot be mem_hi, it must be mem_hi - size. This change will solve (1). As for (2), it is very interesting, would there be a performance difference? I'll update the code with the changes. – sturcotte06 Aug 23 '19 at 23:25

if (mem_low >= mem_hi || mem_hi < mem_low)

The second part of that if is completely redundant.