Seg faults in merge and quick sort

[ralphedge]

These sorts work fine on 100000 ints but if I go much higher they will
both segmentation fault

**************************MERGESORT*********************

mergesort(int *a, int size) //a is pointer to the array, size is # of
elements
{

int b[(size/2)];
int c[(size-(size/2))];
int *bp;
int *cp;
int x;
int y;
bp = b;
cp = c;

if(size > 1)
{

for(x = 0; x < (size/2); x++)
{
b[x] = *(a + x);

}
for(y = 0; y < (size - (size/2)); y++)
{
c[y] = *(a + x);
x++;
}

mergesort(bp, (size/2));
mergesort(cp, (size - (size/2)));
merge(a, bp, cp, size);
}
}

merge(int *a, int *b, int *c, int size)
{
int i = 0, j = 0, k = 0;
while(i < (size/2) && j < (size - (size/2)))
{
if(*(b + i) < *(c + j))
{
*(a + k) = *(b + i);
i++;
}
else
{
*(a + k) = *(c + j);
j++;
}
k++;
}
if(i == (size/2))
{
while(j < (size - (size/2)))
{
*(a + k) = *(c + j);
k++;
j++;
}
}
else
{
while(i < (size/2))
{
*(a + k) = *(b + i);
k++;
i++;
}
}
}
*******************************************

********************QUICKSORT*****************



quicksort(int *a, int size)
{
q_sort(a, 0, size - 1);
}

q_sort(int *a, int l, int r)
{
int s;
//printf("\n%d - size", (r - l));
if(l < r)
{
s = partition(a, l, r);
q_sort (a, l, s - 1);
q_sort(a, s + 1, r);
}
}

int partition(int *a, int l, int r)
{
int i, j, p;
p = *(a + l);
i = l;
j = r + 1;
while(1 < 2)
{
do ++i;
while(*(a + i) <= p && i <= r);
do --j;
while (*(a + j) > p && j >=l);
if(i >= j) break;
swap(a, i, j);
}
swap(a, l, j);
return j;
}

swap(int *a, int b, int c)
{
int temp = *(a + b);
*(a + b) = *(a + c);
*(a + c) = temp;
}






**********************




here is the code I've been using to test with
******************
main()
{
int size = 100000, a[size], *ap, x;
ap = a;
time_t t0, t1;
clock_t c0, c1;

for(x = 0; x < size; x++) //set array in reverse order
{
a[x] = random()%size;
}
t0 = time(NULL);
c0 = clock();
printf("\nMergesorting\n");
mergesort(ap, size);
t1 = time(NULL);
c1 = clock();
/*for(x = 0; x < size; x++) //print contents of array
{
printf("\n%d", a[x]);
}*/
printf("\nMergesort(%d items)\nTime Difference: %f\tClock Cycle
Difference: %f\n",size, (float) (t1-t0),(float) (c1-c0));
size = 100000;
for(x = 0; x < size; x++) //set array in random order
{
a[x] = random()%size;
}

t0 = time(NULL);
c0 = clock();
quicksort(ap, size);
t1 = time(NULL);
c1 = clock();
/*for(x = 0; x < size; x++) //print contents of array
{
printf("\n -%d", a[x]);
}*/

printf("\nQuicksort(%d items)\nTime Difference: %f\tClock Cycle
Difference: %f\n",size, (float) (t1-t0),(float) (c1-c0));
}

****************************

Any idea why I'm getting seg errors?

 

[Mike Wahler]

These sorts work fine on 100000 ints but if I go much higher they will
both segmentation fault

Post code that compiles, and maybe we'll have
a chance at helping find the problem.

A few things that stand out in your code:

-There are no declarations in scope for the
standard library functions you use. This can
often lead to unexpected behavior, and for
variadic functions such as 'printf()' the
behavior is undefined.

-The number of elements in an array definition
must be specified with a constant expression,
unless using a C99 compiler. Since the 'implicit
int' return type is not allowed by C99, it doesn't
appear you're using one. Perhaps you're using
some nonstandard feature of your compiler.

-Sizes of things (such as arrays) should be declared
with type 'size_t', not 'int'. Only 'size_t' is
guaranteed to be able to represent every possible
object size for a given implementation. If a signed
type such as 'int' is assigned a value outside its
range, the behavior is undefined. ("overflow" only
has a defined behavior for unsigned types).

I didn't even look at the logic of your code, too
many other fundamental issues need fixing first.


-Mike

 

[dcorbit]

/*
** There is still lots of room for improvement here. You were missing
header files
** and prototypes, and had implicit declaration of function types.
** You were getting segfaults because of the size of your automatic
variables.
** You should do a test to prove that the data is sorted.
** You should try other distributions besides random (your comments
about
** creating a reversed partition were wrong...) but creating a reversed
partition
** is a very good idea [hint -- this onerous version of qsort will
positively blow chunks]
*/

#include <stdlib.h>

extern void merge(int *, int *, int *, int);
extern void mergesort(int *, int);
extern int partition(int *, int, int);
extern void q_sort(int *, int, int);
extern void quicksort(int *, int);
extern void swap(int *, int, int);

void mergesort(int *a, int size)
{
int *b;
int *c;
int *bp;
int *cp;
int x;
int y;

b = malloc((size / 2) * sizeof *b);
c = malloc((size - (size / 2)) * sizeof *c);
bp = b;
cp = c;

if (size > 1) {
for (x = 0; x < (size / 2); x++) {
b[x] = *(a + x);
}
for (y = 0; y < (size - (size / 2)); y++) {
c[y] = *(a + x);
x++;
}
mergesort(bp, (size / 2));
mergesort(cp, (size - (size / 2)));
merge(a, bp, cp, size);
}
}

void merge(int *a, int *b, int *c, int size)
{
int i = 0,
j = 0,
k = 0;
while (i < (size / 2) && j < (size - (size / 2))) {
if (*(b + i) < *(c + j)) {
*(a + k) = *(b + i);
i++;
} else {
*(a + k) = *(c + j);
j++;
}
k++;
}
if (i == (size / 2)) {
while (j < (size - (size / 2))) {
*(a + k) = *(c + j);
k++;
j++;
}
} else {
while (i < (size / 2)) {
*(a + k) = *(b + i);
k++;
i++;
}
}
}

void quicksort(int *a, int size)
{
q_sort(a, 0, size - 1);
}

void q_sort(int *a, int l, int r)
{
int s;
if (l < r) {
s = partition(a, l, r);
q_sort(a, l, s - 1);
q_sort(a, s + 1, r);
}
}

int partition(int *a, int l, int r)
{
int i,
j,
p;
p = *(a + l);
i = l;
j = r + 1;
while (1 < 2) {
do
++i;
while (*(a + i) <= p && i <= r);
do
--j;
while (*(a + j) > p && j >= l);
if (i >= j)
break;
swap(a, i, j);
}
swap(a, l, j);
return j;
}

void swap(int *a, int b, int c)
{
int temp = *(a + b);
*(a + b) = *(a + c);
*(a + c) = temp;
}

#ifdef UNIT_TEST

#include <stdio.h>
#include <time.h>

int main(int argc, char **argv)
{
int size = 100000;
int *a;
int *ap,
x;
time_t t0,
t1;
clock_t c0,
c1;

if (argc > 0) {
int tsize;
tsize = atoi(argv[1]);
if (tsize > 0) {
size = tsize;
} else {
printf("Invalid size of %d specified. Using 10000.\n",
tsize);
}
}
a = malloc(size * sizeof *a);
if (a == NULL) {
puts("ERROR: Out of memory.");
exit(EXIT_FAILURE);
}
ap = a;
for (x = 0; x < size; x++) {
a[x] = rand() % size;
}
t0 = time(NULL);
c0 = clock();
printf("\nMergesorting\n");
mergesort(ap, size);
t1 = time(NULL);
c1 = clock();
printf("\nMergesort(%d items)\nTime Difference: %f\tClock Cycle
Difference: %f\n",
size, (float) (t1 - t0), (float) (c1 - c0));

for (x = 0; x < size; x++) {
a[x] = rand() % size;
}

t0 = time(NULL);
c0 = clock();
quicksort(ap, size);
t1 = time(NULL);
c1 = clock();
printf("\nQuicksort(%d items)\nTime Difference: %f\tClock Cycle
Difference: %f\n",
size, (float) (t1 - t0), (float) (c1 - c0));
return 0;
}
#endif
/*
C:\tmp>cl /W4 /Ox /DUNIT_TEST stest.c
Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 14.00.50727.42
for 80x86
Copyright (C) Microsoft Corporation. All rights reserved.

stest.c
stest.c(91) : warning C4127: conditional expression is constant
Microsoft (R) Incremental Linker Version 8.00.50727.42
Copyright (C) Microsoft Corporation. All rights reserved.

/out:stest.exe
stest.obj

C:\tmp>stest -9
Invalid size of -9 specified. Using 10000.

Mergesorting

Mergesort(100000 items)
Time Difference: 0.000000 Clock Cycle Difference: 93.000000

Quicksort(100000 items)
Time Difference: 0.000000 Clock Cycle Difference: 0.000000

C:\tmp>stest frog
Invalid size of 0 specified. Using 10000.

Mergesorting

Mergesort(100000 items)
Time Difference: 0.000000 Clock Cycle Difference: 93.000000

Quicksort(100000 items)
Time Difference: 0.000000 Clock Cycle Difference: 16.000000

C:\tmp>stest 0
Invalid size of 0 specified. Using 10000.

Mergesorting

Mergesort(100000 items)
Time Difference: 0.000000 Clock Cycle Difference: 109.000000

Quicksort(100000 items)
Time Difference: 0.000000 Clock Cycle Difference: 16.000000

C:\tmp>stest 1000000

Mergesorting

Mergesort(1000000 items)
Time Difference: 1.000000 Clock Cycle Difference: 1032.000000

Quicksort(1000000 items)
Time Difference: 0.000000 Clock Cycle Difference: 141.000000

C:\tmp>stest 10000000

Mergesorting

Mergesort(10000000 items)
Time Difference: 24.000000 Clock Cycle Difference: 23391.000000

Quicksort(10000000 items)
Time Difference: 4.000000 Clock Cycle Difference: 3703.000000

*/

 

[ralphedge]

Thanks for all the help...one more question

Trying to figure out a better way to time the sorting, but there is no
gethrtime on this computer(running MAC OS)

Any suggestions?(is running sorts for small numbers several times and
taking the average the only way, or is there something else I may be
able to use?)

 

[pete]

Thanks for all the help...one more question

Trying to figure out a better way to time the sorting, but there is no
gethrtime on this computer(running MAC OS)

Any suggestions?(is running sorts for small numbers several times and
taking the average the only way, or is there something else I may be
able to use?)

http://www.mindspring.com/~pfilandr/C/e_driver/
http://www.mindspring.com/~pfilandr/C/e_driver/e_driver.c

loop_time = sort_time(s_L, s, n, 0, loops, &sort_error);

s_time = sort_time(s_L, s, n, sort, loops, &sort_error)

s_time -= loop_time;

double sort_time(struct sf *s_L, e_type **s, size_t nmemb,
size_t sort, long unsigned loops, int *sort_error)
{
size_t i;
clock_t start, stop;

start = clock();
while (start == clock()) {
;
}
start = clock();
while (loops-- != 0) {
copyarray(s[1], s[2], nmemb);
s_L[sort].sortfunc(s[1], nmemb);
}
stop = clock();
*sort_error = 0;
switch (sort) {
case 0:
break;
case 1:
for (i = 1; nmemb > i; ++i) {
if (GT(s[1] + i - 1, s[1] + i)) {
*sort_error = 1;
break;
}
}
copyarray(s[0], s[1], nmemb);
break;
default:
if (comparray(s[0], s[1], nmemb) != 0) {
*sort_error = 2;
}
break;
}
return (double)(stop - start) / (double)CLOCKS_PER_SEC;
}

 

[CBFalconer]

Trying to figure out a better way to time the sorting, but there
is no gethrtime on this computer(running MAC OS)

What sorting? Quote sufficient material so that your posting makes
some sense.

 

[ralphedge]

The mergesort and quicksort that I originally posted about...

 

[Bill Pursell]

(e-mail address removed) should have written (but didn't because
he top-posted instead):

The mergesort and quicksort that I originally posted about...

A few rules of thumb:
1) Don't top-post.
2) Keep context in the article.
3) Remove other people's signature blocks from your response.

 

[Ian Collins]

The mergesort and quicksort that I originally posted about...

Which doesn't compile. You realy have to post code that compiles to get
any help.

 

[CBFalconer]

The mergesort and quicksort that I originally posted about...

Rude top-posting fixed again. Don't top-post. Your reply belongs
after, or possibly intermixed with, the snipped material to which
you reply.

Your original post has nothing to do with it. It is long gone from
here, if it ever arrived. Usenet is not a reliable medium. Google
is not a respectable interface to Usenet. Your articles should
stand by themselves, because there is no guarantee that any other
articles are visible to the reader. That is the purpose of
quoting.

Get yourself a proper newsreader. Thunderbird from mozilla.org
comes to mind. If your ISP is so faulty that it doesn't provide a
newserver, try teranews.com.

 

[Richard Heathfield]

Ian Collins said:

Which doesn't compile. You realy have to post code that compiles to get
any help.

....unless, of course, the question is "why won't this !$&*!%)&$ compile?"

 

[Peter Shaggy Haywood]

Groovy hepcat (e-mail address removed) was jivin' on 20 Oct 2006 14:00:44
-0700 in comp.lang.c.
Seg faults in merge and quick sort's a cool scene! Dig it!

These sorts work fine on 100000 ints but if I go much higher they will
both segmentation fault

**************************MERGESORT*********************

mergesort(int *a, int size) //a is pointer to the array, size is # of
elements

// comments are invalid in C90. Implicit int return type is invalid
in C99. Are you writing C90 or C99 code? Either way you have invalid
code.
Don't post code with // comments here. They have a tendancy to wrap,
making it hard to copy, paste and compile your code.
You have an int function (in C90, but nothing valid in C99), but are
not returning anything from it. This is invalid. Perhaps you want a
void function instead?

void mergesort(int *a, int size)

{

int b[(size/2)];
int c[(size-(size/2))];

VLAs are invalid in C90.

int *bp;
int *cp;
int x;
int y;
bp = b;
cp = c;

What's the point of that? As far as I can see you're not using bp
and cp, except to pass them to mergesort(). Why not just pass b and c
instead?

if(size > 1)
{

for(x = 0; x < (size/2); x++)
{
b[x] = *(a + x);

What's with the *(a + x) notation? It's not wrong; but it is
inconsistent when you have b[x]. What's wrong with b[x] = a[x] or
(less clearly) *(b + x) = *(a + x)?

}
for(y = 0; y < (size - (size/2)); y++)
{
c[y] = *(a + x);
x++;
}

mergesort(bp, (size/2));
mergesort(cp, (size - (size/2)));

There's no declaration of mergesort() in scope.

merge(a, bp, cp, size);

There's no declaration of merge() in scope.

}
}

merge(int *a, int *b, int *c, int size)

Once again, this is invalid: int function (in C90) without returning
anything. Want a void function?

void merge(int *a, int *b, int *c, int size)

{
int i = 0, j = 0, k = 0;
while(i < (size/2) && j < (size - (size/2)))
{
if(*(b + i) < *(c + j))
{
*(a + k) = *(b + i);
i++;
}
else
{
*(a + k) = *(c + j);
j++;
}
k++;
}
if(i == (size/2))
{
while(j < (size - (size/2)))
{
*(a + k) = *(c + j);
k++;
j++;
}
}
else
{
while(i < (size/2))
{
*(a + k) = *(b + i);
k++;
i++;
}
}
}

********************QUICKSORT*****************

quicksort(int *a, int size)

Once again, this is invalid: int function (in C90) without returning
anything. Want a void function?

void quicksort(int *a, int size)

{
q_sort(a, 0, size - 1);

There's no declaration of q_sort() in scope.

}

q_sort(int *a, int l, int r)

Once again, this is invalid: int function (in C90) without returning
anything. Want a void function?

void q_sort(int *a, int l, int r)

{
int s;
//printf("\n%d - size", (r - l));

If you must comment things out, cut them out altogether before
posting. Otherwise they just clutter the code.

if(l < r)
{
s = partition(a, l, r);
q_sort (a, l, s - 1);
q_sort(a, s + 1, r);

There's no declaration of q_sort() in scope.

}
}

int partition(int *a, int l, int r)
{
int i, j, p;
p = *(a + l);
i = l;
j = r + 1;
while(1 < 2)
{
do ++i;
while(*(a + i) <= p && i <= r);
do --j;
while (*(a + j) > p && j >=l);
if(i >= j) break;
swap(a, i, j);

There's no declaration of swap() in scope.

}
swap(a, l, j);

There's no declaration of swap() in scope.

return j;
}

swap(int *a, int b, int c)

Once again, this is invalid: int function (in C90) without returning
anything. Want a void function?

void swap(int *a, int b, int c)

{
int temp = *(a + b);
*(a + b) = *(a + c);
*(a + c) = temp;
}

main()

Once again, you should specify the return type to be C99 compatible.
It is a good idea in C90 too. In either case, main() should return an
int. And do remember to return a value. Portable and valid return
values include 0, EXIT_SUCCESS and EXIT_FAILURE (the latter two
defined in stdlib.h).

int main(void)

{
int size = 100000, a[size], *ap, x;
ap = a;
time_t t0, t1;
clock_t c0, c1;

time_t and clock_t are undeclared. They're not built-in types,
y'know. You have to define them by including time.h. You also need
this header for the time() and clock() functions.

for(x = 0; x < size; x++) //set array in reverse order
{
a[x] = random()%size;
}
t0 = time(NULL);
c0 = clock();

There's no declaration of time() or clock() in scope. See above.

printf("\nMergesorting\n");
mergesort(ap, size);
t1 = time(NULL);
c1 = clock();
/*for(x = 0; x < size; x++) //print contents of array
{
printf("\n%d", a[x]);
}*/
printf("\nMergesort(%d items)\nTime Difference: %f\tClock Cycle
Difference: %f\n",size, (float) (t1-t0),(float) (c1-c0));

Look what you've done! You've created a string literal so big it
wraps. This will not compile when copy/paste/compiled. Break large
string literals down before posting. Eg.:

printf("\nMergesort(%d items)\nTime Difference: %f\tClock "
"Cycle Difference: %f\n",
size, (float) (t1-t0), (float) (c1-c0));

Adjacent string literals are merged into a single string, thus what
looks like two separate strings here actually end up as a single
string.
Also, these casts are rather pointless. t0 and t1 are time_t, which
might be an integer type. In that case t1 - t0 would be calculated in
integer arithmetic. You then cast the resulting integer to float and
print the value as double. (printf()'s %f conversion specifier is for
double, not float. But that's sort of OK, because floats are promoted
to double when passed to a variadic function such as printf().
However, double would be a better type to cast to, to avoid the need
for promotion.) Now, perhaps what you really need is (double)t1 -
(double)t0. This casts t1 and t0 to double *before* the calculation
takes place. Thus the calculation is done in double precision floating
point arithmetic, and you get a double result. Remember:

(type_X)(a - b)

means subtract a from b and then cast the result to type_X, whereas:

(type_X)a - (type_X)b

means cast a and b to type_X and then subtract the result of the
former cast from the result of of the latter. The ultimate results are
very different.
Anyhow, it is rather pointless to do any casting anyhow. You're
subtracting (what might be) an integer from (what might be) an
integer. What possible benefit can be gained by casting to a floating
type? To get the difference between two time_t values as a floating
value representing seconds (which makes a little more sense), you
should use difftime().
Just one more thing about the above printf() statement. You need to
include stdio.h for a prototype of printf(). Otherwise you invoke
undefined behaviour.

size = 100000;
for(x = 0; x < size; x++) //set array in random order
{
a[x] = random()%size;

There's no declaration of random() in scope. It is not a standard
function, and you haven't defined it yourself.

}

t0 = time(NULL);
c0 = clock();
quicksort(ap, size);
t1 = time(NULL);
c1 = clock();
/*for(x = 0; x < size; x++) //print contents of array
{
printf("\n -%d", a[x]);
}*/

printf("\nQuicksort(%d items)\nTime Difference: %f\tClock Cycle
Difference: %f\n",size, (float) (t1-t0),(float) (c1-c0));

See above.

return 0;

}

You need to indent better and more consistently. You should use more
white space, and use it more logically and consistently. Code that is
ugly or poorly laid out is harder to read and understand than nicely
formatted code.

Any idea why I'm getting seg errors?

Are you sure you can create automatic arrays as large as 100000 *
sizeof(int)? My guess is that your implementation allocates automatic
variables on a stack, and that you are overflowing the stack. Of
course, this is just a guess. I haven't paid too much attention to
your program's logic. (That's what comes from writing code that's
poorly laid out. If you make it hard for us to read, we very often
just couldn't be bothered trying to figure it out.) I might have
missed something that could cause a segfault.

--

Dig the even newer still, yet more improved, sig!

http://alphalink.com.au/~phaywood/
"Ain't I'm a dog?" - Ronny Self, Ain't I'm a Dog, written by G. Sherry & W. Walker.
I know it's not "technically correct" English; but since when was rock & roll "technically correct"?

 

[Dave Thompson]

These sorts work fine on 100000 ints but if I go much higher they will
both segmentation fault

Your mergesort allocates in aggregate about 2N worth of temporaries at
one time, in addition to N in main(), on the stack. Assuming 8-bit
byte and 32-bit int as are pretty widespread today but not universal,
that's 1.2MB. Some (many?) implementations (and the platforms they run
on) have stacksize limits significantly less than the address-space
because it is assumed that 'runaway' stack usage is likely a bug
and/or to allow for multiple threads each with their own stack. You
don't identify your implementation but there may well be an
implementation dependent way of increasing the stacksize.

Alternatively, using malloc as suggested by Dann Corbit will often
allow much larger total allocation (from heap space) but: (1) you
should still check for failure and do something more intelligent than
using a failed allocation, at least output a clear error message
before suiciding; and (2) you should free() before returning from each
level as otherwise your total (cumulative) allocation is roughly N *
log2 N actual data (not N * (2+eps)) plus a _lot_ of overhead for the
huge number of small allocations. That last you could avoid by
switching to something else, even bubblesort, below some floor like 8
or 16; this is often a good idea in any case as the k for the 'good'
O(N logN) methods is usually higher than for the simple O(bad) ones.

Alternatively alternatively, since these allocations are strictly LIFO
and of one known element type and of a knowable total, you could do
your own ad-hoc allocation out of a single large static array, or
perhaps a single large malloc'ed space, with nearly no overhead:

int tempspace [100000*21/10]; /* slop to allow for quantizing
on the different call paths; this is probably more than needed
but it's not worth it to me to do the exact analysis */
long avail = 100000*21/10;

/* to be pedantic, those constant expressions could fail on a machine
with 17-bit to 20-bit ints if the compiler doesn't protect itself as
any sensible one will; to be absolutely safe suffix with L */

void mergesort (int *a, size_t n)
{
int *b = & tempspace [ avail -= n/2 ];
int *c = & tempspace [ avail -= n - n/2 ];
/* or int * b = tempspace + (avail -= n/2) etc. if you prefer */
assert (avail >= 0); /* just in case, should never fail */
... logic including recursive calls ...
avail += n;
}

You can also simplify things slightly (with any allocation method) by
allocating _one_ temporary of size n and passing halves in the
recursive calls and to merge, and it simplifies merge to pass it both
half-lengths instead of writing out (and perhaps actually executing)
the split computation in several places:
int b [n] or int *b = as above;
memcpy (b, a, n * sizeof *b);
mergesort (b+0, n/2);
mergesort (b+n/2, n-n/2);
merge (a, b, n/2, b+n/2, n-n/2);

And I see (only?!) Shaggy has noted that *(ary_or_ptr + sub) is
(exactly!) the same in C as ary_or_ptr[sub], but the latter is more
common, conventional, and familiar and so usually preferable.

- David.Thompson1 at worldnet.att.net

 

[pete]

Dave Thompson wrote:

void mergesort (int *a, size_t n)

You can also simplify things slightly (with any allocation method) by
allocating _one_ temporary of size n and passing halves in the
recursive calls and to merge, and it simplifies merge to pass it both
half-lengths instead of writing out (and perhaps actually executing)
the split computation in several places:

It makes more sense to allocate one temporary
of size n/2 for the first half of the array
and to leave the second half in place.

/* BEGIN m_sort.h */

#ifndef H_M_SORT_H
#define H_M_SORT_H

#include <stddef.h>
/*
** m_sort is a stable,
** merge/insertion sort function.
*/
void m_sort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));

#endif

/* END m_sort.h */

/* BEGIN m_sort.c */

#include <stdlib.h>
#include <assert.h>

#include "m_sort.h"
#include "i_sort.h"

#define TOO_SMALL 1

#define BYTE_CPY(A, B) \
{ \
p1 = (A); \
p2 = (B); \
end = p2 + size; \
do { \
*p1++ = *p2++; \
} while (p2 != end); \
}

static void merg(unsigned char *base, unsigned char *buff,
size_t nmemb, size_t size,
int (*compar)(const void *, const void *));

void m_sort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
assert(TOO_SMALL >= 1);
if (nmemb > TOO_SMALL) {
void *buff = malloc(nmemb / 2 * size);

if (buff != NULL) {
merg(base, buff, nmemb, size, compar);
free(buff);
} else {
/*
** If malloc returns NULL,
** then you might want to handle it differently.
*/
i_sort(base, nmemb, size, compar);
}
} else {
i_sort(base, nmemb, size, compar);
}
}

static void merg(unsigned char *base, unsigned char *buff,
size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
if (nmemb > TOO_SMALL) {
unsigned char *p1, *p2, *end, *mid_ptr;
size_t const half_nmemb = nmemb / 2;
size_t const half_bytes = half_nmemb * size;
unsigned char *const after_buff = buff + half_bytes;
unsigned char *const middle = base + half_bytes;
unsigned char *const after_array = base + nmemb * size;

merg(middle, buff, nmemb - half_nmemb, size, compar);
merg(base, buff, half_nmemb, size, compar);
do {
if (compar(base, middle) > 0) {
mid_ptr = middle;
buff = after_buff;
do {
buff -= size;
mid_ptr -= size;
BYTE_CPY(buff, mid_ptr);
} while (base != mid_ptr);
mid_ptr = middle;
BYTE_CPY(base, mid_ptr);
mid_ptr += size;
base += size;
while (middle != base) {
if (compar(buff, mid_ptr) > 0) {
BYTE_CPY(base, mid_ptr);
mid_ptr += size;
} else {
BYTE_CPY(base, buff);
buff += size;
}
base += size;
}
while (after_buff != buff) {
if (after_array != mid_ptr) {
if (compar(buff, mid_ptr) > 0) {
BYTE_CPY(base, mid_ptr);
mid_ptr += size;
} else {
BYTE_CPY(base, buff);
buff += size;
}
base += size;
} else {
do {
BYTE_CPY(base, buff);
base += size;
buff += size;
} while (after_buff != buff);
break;
}
}
break;
} else {
base += size;
}
} while (middle != base);
} else {
i_sort(base, nmemb, size, compar);
}
}

/* END m_sort.c */

/* BEGIN i_sort.h */

#ifndef H_I_SORT_H
#define H_I_SORT_H

#include <stddef.h>
/*
** i_sort is a stable insertion sort with a qsort interface.
*/
void i_sort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));

#endif

/* END i_sort.h */

/* BEGIN i_sort.c */

#include "i_sort.h"

void i_sort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
unsigned char *array, *high, *low, *p1, *p2, *end, swap;

if (nmemb-- > 1) {
array = base;
do {
low = array;
array += size;
high = array;
while (compar(low, high) > 0) {
p1 = low;
p2 = high;
end = p2 + size;
do {
swap = *p1;
*p1++ = *p2;
*p2++ = swap;
} while (p2 != end);
if (low == base) {
break;
}
high = low;
low -= size;
}
} while (--nmemb != 0);
}
}

/* END i_sort.c */