Merge Sort Question

[shane54747]

Implement the mergesort algorithm in C++ as it sorts the following array into ascending order. List the calls to mergesort and to merge in the order in which they occur.

10, 40, 20, 12, 30, 15

i have completed a human merge and i was wondering if its right

10,40,20,12,30,15

10,40,20,12 30,15

10,40 20,12 30,15

10,40 20,12 30,15

10,40 12,20 15,30

10,12,20,40,15,30

10,12,15,20,30,40


Can anyone provide an algorithm or pseudocode for this problem.

Or a similar merge sort problem as i dont know how to implement it in C++

[maikel]

Im not really sure what you now expect? Read the wikipedia article about mergesort, its pretty much everything you need. If you need more than an algorithm, just say so. Concrete implementation? Mergesort is not the easiest one, but with recursion pretty short to implement.

To begin suppose a[1] ... a[M] and b[1] ... b[N] are sorted arrays of integer we wish to merge to a third array c[1] ... c[M+N]. The following is a direct implementation of the obvious strategy of successfully choosing c for the smallest remaining element of a and b:

i = 1; j = 1;
for (k = 1; k < M+N; k++)
    c[k] = (a[i]<b[j]) ? a[i++] : b[j++];

Do not foget to test if i is less M and j is less N. This example is very simplified. If M < N and i >= M just set c[k] = b[j++].

Got the idea?

Greatings and g'night, Maikel

[tummychow]

If you don't know how the alg works look it up. Pseudocode is all over the net. I bet you could even find a C++ implementation.