hi i really need help i am really lost in this program if any one can help me with it plz contact me on my email <<mail id snipped>>
(using c++ program)
1. Write a computer program that implements the recursive merge sort.
The input to the program must be a small list of elements (e.g. 10 to 20 integer numbers). The program must sort the input list and produce a sorted list using the recursive merge sort.
The program must first display the list to be sorted. The program must also display the sublists into which the original list is split during the recursive merge sort process. The program must also display the lists into which the sublists are subsequently merged to form the final sorted list.
2. Big-O estimate of the merge sort.
Give a big-O estimate of the complexity of the merge sort algorithm that you wrote. Justify your big-O estimate of the complexity of the merge sort algorithm with reference to the splitting process of the merge sort and the subsequent merge of these sublists into the final sorted list as illustrated by your program output

Ironically I just wrote a merge sort program for queues a few days back, I'll send it to you tomorrow when I'm at school.

#include<conio.h>
#include<iostream>

using namespace std;

void swap(int &, int &);
void mergeSort(int [],int, int);
int sliptList(int [], int  , int);

int main()
{
    int size,x;

    int nums[size];

    cout<<"Please enter the size of your number list:  ";
    cin>>size;

    while(size < 10 || size > 20)
    {
               cout<<"\nPlease reenter, the size of your list should be between 10 and 20:  ";
               cin>>size;
               }

               cout<<"\nPlease enter in the number of your list:  ";
               for(x=0; x<size; x++)
               {
                        cin>>nums[x];
                        }
                        cout<<"\nThe list you have entered is:  ";

                        for (x=0; x<size; x++)
                        cout<<nums[x]<< "  ";
                        cout<<"\n\nThe two sublists:  ";

                        for (x=0; x <(size/2); x++)
                        cout<<nums[x]<< "  ";
                        cout<<" || ";  // symbol for seperating the two sublists

                        for (x=(size/2); x <size; x++)
                        cout<<nums[x]<< "  ";

                        mergeSort(nums, 0, size-1);

                        cout<<"\n\nThe final sorted list:  ";
                         for (x=0; x<size; x++)
                        cout<<nums[x]<< "  ";
                        cout<<endl;
                        cout<<"\nThe big O-estimate in merge sort of a list of n-elements is nlog(n)";

                        cout<<"\nBig O-estimate in this case is "<<size<<" log "<<size;
                        getch();
                        }

                    void mergeSort(int nums[] ,int start ,int stop) //it ie the recursive function 
                        {

                             int midpt;
                             if(start < stop)
                             {
                                     int sliptList(int [], int  , int); 
                                      midpt = splitList(nums , start, stop);
                                      mergeSort(nums , start, midpt-1);
                                      mergeSort(nums , midpt+1, stop);
                                      }  // ends if

                                      } // ends mergeSort function

    int splitList(int nums[], int start, int stop) //accepting array of integers and two integers representing
                                                               // the starting and ending subscripts in the list
               {
                    int midval, midpt, mid, x;
                    mid = (start + stop)/ 2; //the middle position

                    swap(nums[start], nums[mid]);
                    midpt = start;
                    midval = nums[start];

                    for(x= start + 1; x<=stop; ++x)
                    {
                           if(nums[x] < midval)
                           { 
                                     ++midpt;
                                     swap(nums[midpt],nums[x]);
                                     }
                                     }

                                     swap(nums[start], nums[midpt]);

                                     return midpt;
                                     }


                       void swap(int &val1, int &val2)
                       {
                            int temp;
                            temp = val1;
                            val1 = val2;
                            val2 = temp;
                            }

Edited 3 Years Ago by Reverend Jim: Fixed formatting

This article has been dead for over six months. Start a new discussion instead.