Can someone point me in the right direction on implementing a merge sort.
Here is what the main program will look like. THanks.

``````int main(void)
{
int ar[100];

int i, v, len;

for (i=0; i<100; i++) {
cout << "enter a number (-1 to quit): ";
cin >> v;

if (v < 0) break;

ar[i] = v;
}

len = i;

cout << "main:  before sort:\n";
for (i=0; i<len; i++) {
cout << "main:  ar[" << i << "] = " << ar[i] << endl;
}

mergesort ms(ar, len);

cout << "main:  after sort:\n";
for (i=0; i<len; i++) {
cout << "main:  ar[" << i << "] = " << ar[i] << endl;
}``````

## All 3 Replies

Regarding the merge sort u shud first specify do u want 2-way merge sort , 3-way merge or n-way.well merge sort algo is as follows:

Function Mergesort (field, lower, upper)
if lower = upper then do nothing (field is sorted)
else
middle = (upper + lower)/2
Mergesort (field, lower, middle)
Mergesort (field, middle+1, upper)
Merge (field, lower, middle, upper)
return field

Function Merge (field, lower, middle, upper)
Let ileft = lower, iright = middle+1, ihelp = lower
While ileft ≤ middle AND iright ≤ upper do
if field[ileft] ≤ field[iright] then
ifield[ihelp] = field
increment ihelp, increment iright
While ileft ≤ middle do
ifield[ihelp] = field[ileft]
increment ihelp, increment ileft
While iright ≤ upper do
ifield[ihelp] = field[iright]
increment ihelp, increment iright
For ihelp from lower to upper do
field[ihelp] = ifield[ihelp]
return field
Thus in plain english do the following steps.

First divide the array into two approximately equal large sub-arrays.

Sort each of these sub-arrays separately.

Merge the resolting sorted sub-arrays into the resulting subarray

``````#include <iostream.h>
int mergesort;
int main(void)
{
int ar[100];

int i, v, len;

for (i=0; i<100; i++) {
cout << "enter a number (-1 to quit): ";
cin >> v;

if (v < 0) break;

ar[i] = v;
}

len = i;

cout << "main:  before sort:\n";
for (i=0; i<len; i++) {
cout << "main:  ar[" << i << "] = " << ar[i] << endl;
}

mergesort;

cout << "main:  after sort:\n";
for (i=0; i<len; i++) {
cout << "main:  ar[" << i << "] = " << ar[i] << endl;
}
}
``````
``````    #include <iostream.h>
int mergesort;
int main(void)
{
int ar[100];

int i, v, len;

for (i=0; i<100; i++) {
cout << "enter a number (-1 to quit): ";
cin >> v;

if (v < 0) break;

ar[i] = v;
}

len = i;

cout << "main:  before sort:\n";
for (i=0; i<len; i++) {
cout << "main:  ar[" << i << "] = " << ar[i] << endl;
}

mergesort;

cout << "main:  after sort:\n";
for (i=0; i<len; i++) {
cout << "main:  ar[" << i << "] = " << ar[i] << endl;
}
}
``````

It is not April 1 yet!!!

Even if you had this magical global integer called mergesort, you still might have to tell it what to sort. Dream on!!

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.