So I've managed to … - QuestionCove
OpenStudy (anonymous):

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?

5 years ago
OpenStudy (anonymous):

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

5 years ago
OpenStudy (anonymous):

?

5 years ago
OpenStudy (anonymous):

Merge sort isn't that hard to code.

5 years ago
OpenStudy (anonymous):

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

5 years ago
OpenStudy (anonymous):

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

5 years ago
OpenStudy (anonymous):

My personal preference is always quick sort.

5 years ago
OpenStudy (anonymous):

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

5 years ago
OpenStudy (anonymous): 5 years ago
OpenStudy (across):

Do you like recursion?

5 years ago
OpenStudy (anonymous):

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

5 years ago
OpenStudy (anonymous): 5 years ago
OpenStudy (anonymous):

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

5 years ago
OpenStudy (anonymous):

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)

5 years ago
OpenStudy (anonymous):

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

5 years ago
OpenStudy (anonymous):

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

5 years ago
OpenStudy (anonymous):

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

5 years ago
OpenStudy (anonymous):

but it took me hours to stop all the segfaults

5 years ago
OpenStudy (anonymous):

I had most trouble with the merge step

5 years ago
OpenStudy (asnaseer):

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

5 years ago
OpenStudy (asnaseer):

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

5 years ago
OpenStudy (anonymous):

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

5 years ago
OpenStudy (anonymous):

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

5 years ago
OpenStudy (anonymous): 5 years ago
OpenStudy (anonymous):

I can give you if you want ?

5 years ago
OpenStudy (anonymous):

sure

5 years ago
OpenStudy (anonymous):

I wanna go to bed tonight, knowing how to mergesort

5 years ago
OpenStudy (anonymous):

But it is the solution to this problem: www.spoj.pl/problems/MERGSORT/

5 years ago
OpenStudy (asnaseer):

want to mergesort in your sleep? :D

5 years ago
OpenStudy (anonymous):

haha :D

5 years ago
OpenStudy (anonymous):

I see algorithm pseudocode in my dreams

5 years ago
OpenStudy (asnaseer):

you need to see a doctor ;-)

5 years ago
OpenStudy (anonymous):

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.

5 years ago
OpenStudy (anonymous):

that's it, right?

5 years ago
OpenStudy (anonymous):

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!

5 years ago
OpenStudy (anonymous):

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

5 years ago
OpenStudy (anonymous):

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 :)

5 years ago
OpenStudy (anonymous):

ooh it's even commented!

5 years ago
OpenStudy (anonymous):

Now logout and let me enjoy being mod :P

5 years ago
OpenStudy (anonymous):

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

5 years ago
OpenStudy (anonymous):

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

5 years ago
OpenStudy (anonymous):

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); }$

5 years ago
OpenStudy (anonymous):

Are you going to logout now ? !!!

5 years ago