How to implement the merge sort? Question: We combine two sorting algorithms, in

Question

How to implement the merge sort?

Question:

We combine two sorting algorithms, insertion-sort and merge-sort as follows:
when the input size is less than 100, we use insertion-sort; otherwise, we use merge-sort. More
specifically, we replace line 1 in Merge-Sort with “if r p >= 100”, and add line 6
“else Insertion-Sort(A, p, r)”. Insertion-Sort(A, p, r) implies performing insertion sort on the
subarray A[p · · · r]. In this lab assignment you will implement this hybrid sorting algorithm.

Code I wrote so far:

#include <iostream>
#include <stdlib.h>
#include <string>

using namespace std;

void MyFunc ( int *array ) {
  
}

int main(int argc,char **argv) {

int *Sequence;
int arraySize;

// Get the size of the sequence
cin >> arraySize;

// Allocate enough memory to store "arraySize" integers
Sequence = new int[arraySize];
  
// Read in the sequence
for ( int i=0; i<arraySize; i++ )
cin >> Sequence[i];

// Run your algorithms to manipulate the elements in Sequence
MyFunc(Sequence);
  
// Output the result
for(int i=0; i<arraySize; i++)
cout << Sequence[i] << endl;
  
// Free allocated space
delete[] Sequence;
}

Explanation / Answer

#include <iostream>

using namespace std;

//Function to merge the two subarrays

void Merge(int *a, int low, int high, int mid)

{

int i, j, k, temp[high-low+1];

i = low;

k = 0;

j = mid + 1;

//merge the two arrays in temp

while (i <= mid && j <= high)

{

if (a[i] < a[j])

{

temp[k] = a[i];

k++;

i++;

}

else

{

temp[k] = a[j];

k++;

j++;

}

}

//add the remaining terms of first array to temp

while (i <= mid)

{

temp[k] = a[i];

k++;

i++;

}

//add the remaining terms of second array to temp

while (j <= high)

{

temp[k] = a[j];

k++;

j++;

}

// Assign sorted data stored in temp[] to a[].

for (i = low; i <= high; i++)

{

a[i] = temp[i-low];

}

}

//find the subarrays i.e divide the array in two

void MergeSort(int *a, int low, int high)

{

int mid;

if (low < high)

{

mid=(low+high)/2;

// Split the data into two half.

MergeSort(a, low, mid);//recursive function to sort the left subarray

MergeSort(a, mid+1, high);//recursive function to sort the right subarray

// Merge them to get sorted output

Merge(a, low, high, mid);

}

}

int main()

{

int n, i;

cout<<" Enter the number of data element to be sorted: ";

cin>>n;

int arr[n];

for(i = 0; i < n; i++)

{

cout<<"Enter element "<<i+1<<": ";

cin>>arr[i];

}

MergeSort(arr, 0, n-1);

// Printing the sorted data.

cout<<" Sorted Data ";

for (i = 0; i < n; i++)

cout<<"->"<<arr[i];

return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.