By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
432,403 Members | 855 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 432,403 IT Pros & Developers. It's quick & easy.

My merge-sort implementation. Feedback appreciated!

P: n/a
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/c...ort-0.1.tar.gz

Thankful for any advice :)

- uppe

Jun 9 '06 #1
Share this Question
Share on Google+
5 Replies


P: n/a
"uppe" <je*************@gmail.com> wrote in message
news:11**********************@j55g2000cwa.googlegr oups.com...
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/c...ort-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?
Jun 9 '06 #2

P: n/a
"Dann Corbit" <dc*****@connx.com> writes:
"uppe" <je*************@gmail.com> wrote in message
news:11**********************@j55g2000cwa.googlegr oups.com...
Anyway, the source code is available here:
http://www.student.lu.se/~mah06jfo/c...ort-0.1.tar.gz
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/.../kernel/list.c
--
"I'm not here to convince idiots not to be stupid.
They won't listen anyway."
--Dann Corbit
Jun 9 '06 #3

P: n/a
Ben Pfaff wrote:

"Dann Corbit" <dc*****@connx.com> writes:
"uppe" <je*************@gmail.com> wrote in message
news:11**********************@j55g2000cwa.googlegr oups.com...
Anyway, the source code is available here:
http://www.student.lu.se/~mah06jfo/c...ort-0.1.tar.gz

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


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.

--
pete
Jun 9 '06 #4

P: n/a
pete <pf*****@mindspring.com> writes:
Ben Pfaff wrote:

"Dann Corbit" <dc*****@connx.com> writes:
> "uppe" <je*************@gmail.com> wrote in message
> news:11**********************@j55g2000cwa.googlegr oups.com...
>> Anyway, the source code is available here:
>> http://www.student.lu.se/~mah06jfo/c...ort-0.1.tar.gz

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


To my eye, it looks cleanly written.


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.
--
"...what folly I commit, I dedicate to you."
--William Shakespeare, _Troilus and Cressida_
Jun 9 '06 #5

P: n/a
"Ben Pfaff" <bl*@cs.stanford.edu> wrote in message
news:87************@benpfaff.org...
pete <pf*****@mindspring.com> writes:
Ben Pfaff wrote:

"Dann Corbit" <dc*****@connx.com> writes:

> "uppe" <je*************@gmail.com> wrote in message
> news:11**********************@j55g2000cwa.googlegr oups.com...
>> Anyway, the source code is available here:
>> http://www.student.lu.se/~mah06jfo/c...ort-0.1.tar.gz

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

To my eye, it looks cleanly written.
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.


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...mergesort%29+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.
--
"...what folly I commit, I dedicate to you."
--William Shakespeare, _Troilus and Cressida_

Jun 9 '06 #6

This discussion thread is closed

Replies have been disabled for this discussion.