My merge-sort implementation. Feedback appreciated!

[uppe]

Hey everyone,

I've just finished my implementation of the merge-sort algorithm in C,
and I thought I could ask for some feedback. (One can always improve,
they say)

Right now, the code sorts integers in an ascending order, which
probably isn't very useful on its own.

I know the code works for a reasonable and arbitrary size of input, but
how about using a bignum library (such as gmp) for adding the feature
of sorting inputs of any size? As well as sorting elements of any size.

Since I'm not very experienced with C yet, I could not really see if
there were any chances for memory leaks. Is it true that whenever I use
malloc() without an accompanying free(), a memory leak could occur?

Anyway, the source code is available here:
http://www.student.lu.se/~mah06jfo/code/mergesort-0.1.tar.gz

Thankful for any advice

- uppe

 

[Dann Corbit]

Hey everyone,

I've just finished my implementation of the merge-sort algorithm in C,
and I thought I could ask for some feedback. (One can always improve,
they say)

Right now, the code sorts integers in an ascending order, which
probably isn't very useful on its own.

I know the code works for a reasonable and arbitrary size of input, but
how about using a bignum library (such as gmp) for adding the feature
of sorting inputs of any size? As well as sorting elements of any size.

Since I'm not very experienced with C yet, I could not really see if
there were any chances for memory leaks. Is it true that whenever I use
malloc() without an accompanying free(), a memory leak could occur?

Anyway, the source code is available here:
http://www.student.lu.se/~mah06jfo/code/mergesort-0.1.tar.gz

Thankful for any advice

Always check the return of malloc(). If malloc() fails, take appropriate
action. Filter programs should not pump "Hi there" message to the console.

Use a callback function for comparison. Unless you can make it general
purpose, it does not really have any utility.

There are lots of really good merge sorts around already. What makes this
one special?

 

[Ben Pfaff]

There are lots of really good merge sorts around already. What makes this
one special?

To my eye, it looks cleanly written.

I once wrote a merge sort I'm rather fond of, simply because I
consider it nicely written. It is list_sort(), here:
http://www.stanford.edu/class/cs140/pintos/pintos/src/lib/kernel/list.c

 

[pete]

To my eye, it looks cleanly written.

I'm seeing it differently.
There shouldn't be any malloc calls in merge sort for lists.

The merge() function seems to be copying the lists,
with the insertLast() function,
instead of just merging them.

The split() function mallocs a pointer
which can never be freed.

I think there's a lot of memory leakage there.

 

[Ben Pfaff]

I'm seeing it differently.
There shouldn't be any malloc calls in merge sort for lists.

I didn't really read the code. I just saw that the structure was
a simple set of calls to a simple set of functions, which is a
promising start.

 

[Dann Corbit]

I didn't really read the code. I just saw that the structure was
a simple set of calls to a simple set of functions, which is a
promising start.

I should point out that my intention was not to denigrate the efforts of the
O.P. but to find out why his code was to be recommended or what features he
wanted to highlight. This google query for merge sorting in C yields
305,000 hits for me:
http://www.google.com/search?hl=en&q=("merge+sort"+OR+mergesort)+C

I have perhaps two dozen merge sort implementations that I play with from
time to time (sorting is something of a hobby for me). I was simply curious
about what the author liked abouit his particular implementation.

While I do see a few defects in the code, I agree with Ben that it is a
promising start, at least.