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

[vegaseat]

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