Question

So I've managed to understand all the basic \( O(n^2) \) (except shell sort, but that's a little different) basic comparison sort algorithms. However, although I understand the whole idea of mergesort, I still couldn't figure out how to code it in C. Can anyone help?

Answer 1

Yes I could have, but you stole my mod power, so I won't :P

Answer 2

?

Answer 3

Merge sort isn't that hard to code.

Answer 4

please.... you're like the guru of algorithms here.

Answer 5

it shouldn't be (it's the easiest of the O(nlgn) sorting algorithms) but I'm still having trouble :(

Answer 6

My personal preference is always quick sort.

Answer 7

but I'm only at the merge sort part of the book (quicksort is much later in the book)

Answer 8

http://www.sorting-algorithms.com/merge-sort

Answer 9

Do you like recursion?

Answer 10

the algorithm on that page seems straightforward to translate over to C

Answer 11

http://www.google.com/search?q=recursion

Answer 12

I love recursion, but there is always a chance of stack overflow in recursion.

Answer 13

I love recursive algorithms (too bad they don't perform as well as the iterative/functional version and also chance of exceeding recursion depth and overflowing the stack)

Answer 14

For example if you are looking to implement O(ln) pow(a,b,c) the recursive approach often invoke stack overflow.

Answer 15

pow(a,b,c) is finding \( a^b \% c \)

Answer 16

this is what I've done in C: http://ideone.com/nZRKA it ran alright

Answer 17

but it took me hours to stop all the segfaults

Answer 18

I had most trouble with the merge step

Answer 19

you may be interested at looking at this: http://www.cprogramming.com/tutorial/computersciencetheory/mergesort.html

Answer 20

if you scroll down on that page and look for the "Implementation" section - they provide a simple one for you

Answer 21

originally I had the merge step allocate two buffers for the left and right subarrays.

Answer 22

I think I have something in my archive that I have implemented a year back.

Answer 23

http://www.youtube.com/watch?v=t8g-iYGHpEA

Answer 24

I can give you if you want ?

Answer 25

sure

Answer 26

I wanna go to bed tonight, knowing how to mergesort

Answer 27

But it is the solution to this problem:

www.spoj.pl/problems/MERGSORT/

Answer 28

want to mergesort in your sleep? :D

Answer 29

haha :D

Answer 30

I see algorithm pseudocode in my dreams

Answer 31

you need to see a doctor ;-)

Answer 32

So this is how the merge step of mergesort works:

1. compare the elements at the beginning of each subarray, and place the smallest one in the output buffer. do this until one of the subarrays are empty

2. simply place all the elements in the non-empty subarray into the output buffer.

Answer 33

that's it, right?

Answer 34

then the sorting part is

1. divide the buffer in half
2. merge sort the left half,
3. merge sort the right half
4. merge them!

Answer 35

oh and before all those: check to see if the array only has one element, and return if true (already sorted)

Answer 36

This is the main part of my solution: http://ideone.com/fiY78

I have skimmed the fast i/o routine and the main(); I Hope you could make it work from this :)

Answer 37

ooh it's even commented!

Answer 38

Now logout and let me enjoy being mod :P

Answer 39

Oh yes, I am a fool so I keep everything commented in my archive ;)

Answer 40

I like the idea of mergesort: how it boldly calls itself "mergesort (left, mid); mergesort(mid+1, right);

Answer 41

it seems to be capable of sorting a million 32 bit integers, unlike the isort I came up with :-P

\[#
void isort(void* base, size_t num, size_t size, int (*comparator) (const void*, const void*))
{
void *left, *right, *key;
if ((key = malloc(size)))
{
for (right = (base + size); (size_t) (right - base)/size < num; right += size)
{
memcpy(key, right, size);
for (left = right; left > base && comparator((left - size), key) > 0; left -= size)
{
memcpy(left, left - size, size);
}
memcpy(left, key, size);
}
}
free(key);
}\]

Answer 42

Are you going to logout now ? !!!