Question

USING C++ write a program that creates a modified version of Merge sort in which insertion sort will be used for merging array elements.

Answer 1

#include <iostream>
using namespace std;

void insertion_sort(int array[],int n){
int t,j;
for(int i=0; i<n; i++){
t = array[i];
j = i-1;
while((t<array[j]) && j>=0){
array[j+1] = array[j];
j--;
}
array[j+1] = t;
}
}
//function to merge two sub-arrays
void merge(int array[], int l, int m, int r){
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
//create two temporary arrays
int L[n1], R[n2];
//copy the contents in temporary arrays
for (i = 0; i < n1; i++)
L[i] = array[l + i];
for (j = 0; j < n2; j++)
R[j] = array[m + 1+ j];

i = 0;
j = 0;
k = l;
while (i < n1 && j < n2){
if (L[i] <= R[j]){
array[k] = L[i];
i++;
}
else{
array[k] = R[j];
j++;
}
k++;
}
//if there are any remaining elements of L[], copy then
while (i < n1){
array[k] = L[i];
i++;
k++;
}
//if there are any remaining elements of R[], copy then
while (j < n2){
array[k] = R[j];
j++;
k++;
}
}
//function mergesort
void Merge_Sort(int array[], int l, int r){
if (l < r){

int m = l+(r-l)/2;
// Sort first and second halves
Merge_Sort(array, l, m);
Merge_Sort(array, m+1, r);
  
merge(array, l, m, r);
}
}
//function display to print the contents of the array
void display(int array[], int n){
int i;
for (i=0; i < n; i++)
cout << array[i] <<" ";
cout << endl;
}

int main(){
int n, array[30];
cout<<"Enter the number of elements";
cin>>n;
cout<<"\nEnter elements of array:";
for(int i=0;i<n;i++)
{
cin>>array[i];
}
cout << "\nOriginal array : \n";
display(array, n);
insertion_sort(array, n);
cout << "Sorted array: \n";
display(array, n);
cout << "\n";
}

Output:-

Enter the number of elements 10

Enter elements of array: 10
 23
 21
 12
 34
 16
 2
 7
 1
 19

Original array : 
10 23 21 12 34 16 2 7 1 19 
Sorted array: 
1 2 7 10 12 16 19 21 23 34