#include <iostream>
using namespace std;
void mergesort(int* array ,int count)
{
for(int n=0 ;array[n] > array[n+1];n++ )
{
while(count>=0)
{
for(int o=0 ;array[o] > array[o+1];o++)
{
if(array[n]>array[o])
{
for (int p=array[o]-1; p>=array[n]+1; p--)
{
array[p] = array[p-1];
}
array[n] = array[o];
}
}
count--;
}
}
}
int main()
{
int count = 1;
int array[]={1,2,4,3,5,6,8};
int size;
size = sizeof array/sizeof array[0];
for (int i = 0; i < size-1; i++) // for loop to find how many sorted runs
{
if (array[i] > array[i+1])
count++;
}
cout<<"sorted runs is "<<count<<endl;
int pst = 0; //initialization of position for the start of every runs
int* pos= new int[size]; //creating new array to store the value of new sorted runs position
for (int j = 0; j < size; j++) //loop to find position for the start of sorted runs and store it in pos array
{
if (array[j] > array[j+1])
pos[pst] = j+1;
pst++;
}
cout<<"sorted runs start at index "<< pos[0]<<endl; //printing the first sorted runs,which is index 0
for (int k = 0; k < size-1; k++) //loop to print the rest sorted runs position
{
if (array[k] > array[k+1])
{
cout<<"sorted runs start at index "<< pos[k]<<endl;
}
}
mergesort(array,count);
cout<<"sorted array"<<endl;
for (int q=0; q<size; q++)
{
cout <<array[q] << " ";
}
cout << endl;
return 0;
}