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

cin>>size;

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

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

You neeed to merge the sorted split arrays.

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.