Merge sort

[skeet123]

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

[harshchandra]

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[left]
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

[yb1pls]

#include
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

[vegaseat]

#include 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 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!!